MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does anyone know any undecidable problems in the dynamics of functions (not necessarily monoid homomorphisms or anything) from \Sigma^* to \Sigma^* where \Sigma is a finite set? In particular, I'm wondering if there is an algorithm that takes as input a (computable) function f:Sigma^* \rightarrow \Sigma^, a w \in \Sigma^, and a language L and decides if there is an n such that f^n(w) is an element of L. Does anyone have a reference where questions similar to this are addressed? Thanks.

EDIT: I had to take the dollar signs out of the question. The site was having trouble with the Tex.

share|cite|improve this question
up vote 1 down vote accepted

There is no such algorithm as you request, since if there were, you could solve the halting problem. To see this, consider that the operation of a Turing machine can be viewed as a function $f$ to be iterated on the finite strings representing Turing machine configurations. So, for any TM program and input, let $f$ be the corresponding function for operating this program, let $w$ be the string showing the starting configuration and let L be the language of strings showing the configuration of a program that has just halted. The question of whether $p$ halts on that starting input is the same as the question of whether there is some $f^n(w)\in L$. So there can be no algorithm deciding this.

I think most of the standard classical undecidable questions in computability theory can be similarly translating into this kind of question.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.