Question

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.

Answer 1

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.