An Undecidable Nested Recurrence Relation

Marcel Celaya, Department of Computer Science, University of Victoria, British Columbia, Canada.
Frank Ruskey, Department of Computer Science, University of Victoria, British Columbia, Canada.

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.

Appears as arXiv:1203.0586v1 [math.CO], submitted March 2, 2012.
Submitted to CiE 2012, January 2012.
Accepted for presentation and LNCS publication at Computing in Europe (CiE 2012), part of the Turing Centenary Celebrations. Accepted March 16, 2012.
Appears in Lecture Notes in Computer Science (LNCS) 7318 107-117.
The postscript file.
The pdf file.

Selected Publications that refer to this paper:

Abraham Isgur, Solving Nested Recursions with Trees, PhD Thesis, Mathematics Department, University of Toronto, 2012.
Someday there will be some more!

Back to list of publications.