Dynamical Systems and Program Analysis
summary
Algorithmic verdicts: termination of deterministic linear-update loops is decidable over the reals and rationals and (recently) decidable over the integers for the universal problem; the corresponding initialized termination question reduces to the positivity problem for linear recurrences, decidable only up to small orders (order ≤5) and low-dimensional loops (≤4 variables, ≤8 if diagonalizable). Proofs mix real algebraic-geometry relaxations, Baker/subspace-theorem Diophantine bounds, and construct an explicit convex semi-algebraic invariant whose integer-point emptiness is decidable, while deeper cases hinge on number-theoretic obstacles like transcendence and Diophantine approximation and the critical ratio phenomenon.
AI-written summary · about