Undecidability of restricted uniform recurrence equations (Q1901700): Difference between revisions

A system of recurrence equations is said to be computable if and only if none of its variable instances depends on itself and each of them depends only on finitely many variable instances. The computability of systems of recurrence equations is considered to be the first point of examination when trying to implement an algorithm. In general, when the index domains of a system are allowed to be unbounded and distinct, the computability of such systems may be undecidable. The results presented in this paper essentially demonstrate that the computability of uniform systems of recurrence equations is undecidable even if the number of indices, the number of recurrence equations, the number of variables, and the number of different index domains are bounded by a constant. In particular, we show that the computability of systems of recurrence equations is undecidable for \(\bullet\) affine systems with three indices, one variable, three equations, and three index domains, \(\bullet\) uniform systems with four indices and five index domains, and \(\bullet\) uniform systems with six indices, one variable, seven equations, and seven index domains. The parameters which are not fixed in all the restricted versions are first, the integers involved in the index manipulations, and second, the number of variable instances used in an equation.