An Undecidable Nested Recurrence Relation

摘要

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))) + AA (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.