Re: Computability theory question

Snis Pilbor <snispilbor@xxxxxxxxx> wrote:
Fix a Godel numbering of the computable functions, say phi_n is the
nth computable function.

Let superscripts denote iteration: phi_n^1(i)=phi_n(i), phi_n^j(i) =
phi_n(phi_n^{j-1}(i)).

Is it possible that there is some n, and some k>1, such that for every
i,
phi_n^k(i) = phi_n(i)? (In particular, phi_n is total)

If the answer is "no", then I can prove something nice.. =) Not
homework related.


Hmm, I'm afraid this is very possible: just let n be an index for the
identity function... Sorry...

--
Cheers, Tom

*** PGP Key available at <paetz.sdf-eu.org> ***
.