论文标题
涉及任意实数的线性复发的决策问题
Decision problems for linear recurrences involving arbitrary real numbers
论文作者
论文摘要
我们研究了Skolem问题的可决定性，阳性问题以及在真实计算的位模型中具有实数初始值和实际数量系数的线性复发的最终阳性问题。我们表明，对于每个问题，存在一种正确的部分算法，该算法停止了答案在本地稳定的所有问题实例，从而确定所有三个问题都与人们期望它们在这种情况下一样接近可决定。我们进一步表明，关于阳性问题的算法和最终的积极问题在几乎所有情况下都停止了相对于欧几里得空间的通常的lebesgue度量。相比之下，已知仅对于相当低阶的线性复发而言，已知有理理性或实际代数系数的类似问题是可以决定的。
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.
