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,...,n1}.
We show that the recurrence relation
A(n) = A(n4A(A(n4))) + 4A(A(n4))
+ A(2A(n4A(n2)) + A(n2))
is undecidable by showing how it can be used, together with carefully chosen initial conditions,
to simulate Post 2tag 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.