We study the decidability of the Skolem Problem, the Positivity Problem, and the Ultimate Positivity Problem for linear recurrences with real number initial values and real number coefficients in the bit-model of real computation. We show that for each problem there exists a correct partial algorithm which halts for all problem instances for which the answer is locally constant, thus establishing that all three problems are as close to decidable as one can expect them to be in this setting. We further show that the algorithms for the Positivity Problem and the Ultimate Positivity Problem halt on almost every instance with respect to the usual Lebesgue measure on Euclidean space. In comparison, the analogous problems for exact rational or real algebraic coefficients are known to be decidable only for linear recurrences of fairly low order.
翻译:我们研究了Skolem问题、概率问题和终极概率问题对实际计算模型中真实数字初始值和实际数字系数的线性重现的衰变可能性问题。 我们发现,对于每个问题,都存在一种正确的局部算法,它停止了所有答案本地常态的问题,从而确定了所有这三个问题都接近于衰变的可能性,而人们可以预期它们会在此背景下发生。我们进一步显示,概率问题和超大概率问题的算法几乎都停止了对欧克利底空间通常的Lebesgue测量法的几乎每一种情况。相比之下,准确合理或实际代数系数的类似问题只已知在极低顺序线性重现时才会被衰减。