An Undecidable Nested Recurrence Relation

Details An Undecidable Nested Recurrence Relation An Undecidable Nested Recurrence Relation

2012-03-02

arxiv.org/abs/1203.0586v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An Undecidable Nested Recurrence Relation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Undecidable Nested Recurrence Relation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Undecidable Nested Recurrence Relation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-344668