Undecidability of restricted uniform recurrence equations

DOI10.1007/S002360050053MaRDI QIDQ1901700zbMATH OpenOpenAlexFDO

Authors Egon Wanke

Publication date 19 November 1995

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002360050053

zbMATH Keywords

computabilitysystem of recurrence equationsundecidability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Recurrences (11B37) Decidability (number-theoretic aspects) (11U05)

Review text

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.

Recommendations

• Computability of recurrence equations
• On the Computational Completeness of Equations over Sets of Natural Numbers
• New results on computability of recurrence equations
• Computability of affine non-conditional recurrent systems
• An undecidable nested recurrence relation

Cites work

• Computability of recurrence equations
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• The mapping of linear recurrence equations on regular arrays
• The Organization of Computations for Uniform Recurrence Equations

Cited in

(8)

• Impossibility of finite generation of partial recursive functions by a unary isotone operation
• Computability of affine non-conditional recurrent systems
• Undecidable arithmetic properties of solutions of Fredholm integral equations
• Computations of uniform recurrence equations using minimal memory size
• Decidability of uniform recurrence of morphic sequences
• An undecidable nested recurrence relation
• New results on computability of recurrence equations
• Computability of recurrence equations

This page was built for publication: Undecidability of restricted uniform recurrence equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1901700)