## 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.

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.