Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+ All Title Author Keywords Abstract
 Publish in OALib Journal ISSN: 2333-9721 APC: Only \$99

 Relative Articles Morphic Words and Nested Recurrence Relations Nested Recurrence Relations With Conolly-Like Solutions Recurrence relation for Jones polynomials Some results about Linear Recurrence Relation Homomorphisms Combinatorial interpretation of the recurrence relation for fibonomial coefficients Recurrence relation for relativistic atomic matrix elements Recurrence relation for HOMFLY polynomial and rational specializations A shortened recurrence relation for the Bernoulli numbers Rigidity is undecidable The Recurrence Relation of Irreducible Tensor Operators for O(4) More...

# An Undecidable Nested Recurrence Relation

 Full-Text   Cite this paper

Abstract:

Roughly speaking, a recurrence relation is nested if it contains a subexpression of the form ... A(...A(...)...). Many nested recurrence relations occur in the literature, and determining their behavior seems to be quite difficult and highly dependent on their initial conditions. A nested recurrence relation A(n) is said to be undecidable if the following problem is undecidable: given a finite set of initial conditions for A(n), is the recurrence relation calculable? Here calculable means that for every n >= 0, either A(n) is an initial condition or the calculation of A(n) involves only invocations of A on arguments in {0,1,...,n-1}. We show that the recurrence relation A(n) = A(n-4-A(A(n-4)))+4A(A(n-4)) +A(2A(n-4-A(n-2))+A(n-2)). is undecidable by showing how it can be used, together with carefully chosen initial conditions, to simulate Post 2-tag systems, a known Turing complete problem.

Full-Text