I have a question about the possibility to apply/restate the Kleene fixed point theorem on recursive subsets of computable functions. I don't know if this is trivial and/or if related questions have been already solved. Any suggestion is more than welcome.

Kleene fixed point theorem states that for every total computable function $T_i \simeq \varphi:\mathbb{N}\rightarrow \mathbb{N}$ there exists some $v\in\mathbb{N}$ such that $\forall x, T_{\varphi(v)}(x)\simeq T_v(x)$. That is, the $v$-th ($T_v$) Turing Machine (TM) computes the same function as the $\varphi(v)$-th TM, and $v$ is thus a "fixed point" for the transformation $\varphi$.

Consider now a total computable function $f:\mathbb{N}\rightarrow \mathbb{N}$. The recursive (infinite) set $E=f(\mathbb{N})$ represents the subset of TMs/computable functions, $T_{f(1)}, T_{f(2)}, ..$, we want to consider. Since $E$ is a recursive set, we can use the notation $T^E_i$ to denote $T_{f(i)}$, i.e. $T^E_i$ is the i-th TM/function in $E$. Let $T^E_{i}\simeq\phi$ be a total computable function (if any). Now, it is possible to restate the Kleene fixed point theorem on the set $E$? That is, is it true that there exists some $v\in \mathbb{N}$ such that: $\forall x: T^E_{\phi(v)}(x)\simeq T^E_{v}(x)$? Note that we cannot apply here directly the Kleene's theorem since the property above translates into $\exists v \forall x: T_{f(\phi(v))}(x)\simeq T_{f(v)}(x)$ and the original (standard?) proof seems hard (if not impossible) to recode in this new setting (unless $f$ is assumed to be surjective, in which case the problem becomes trivial).

I don't expect this property to be true for all the possible recursive functions $f$ (it's just my non-expert opinion), so my question is: is it possible to characterize the class of mappings $f$ for which the above property is true? For example, is this property true if we assume that the range of $f$ is a set of total functions?

  • 3
    $\begingroup$ Why is $E$ recursive? It is r.e., obviously, but why recursive? $\endgroup$ – Andrej Bauer Mar 5 '12 at 18:32
  • $\begingroup$ Thanks for pointing out this: E does not need to be recursive. $\endgroup$ – Pietro Mar 7 '12 at 1:56

In general, there will be no such fixed points, even when the range of $f$ consists of programs for total computable functions. The reason is that we can easily compute a list of programs for distinct total functions. That is, we can arrange that $T_{f(n)}\neq T_{f(m)}$ whenever $n\neq m$. For example, we could for each $n$ let $f(n)$ be a program that computes the constant value $n$ function, which would certainly achieve $T_{f(n)}\neq T_{f(m)}$. The point about this now is that if $\varphi$ is a computable function such that $\varphi(v)\neq v$ for every $v$, such as the successor function $\varphi(v)=v+1$, then it follows that $T_{f(\varphi(v))}\neq T_{f(v)}$, and so there is no fixed point in your sense.

Edit. François pointed out in the comments that you want $\varphi$ among the $T_{f(n)}$, a feature my particular example above does not have. But this is easily fixed. Let's use $T_{f(n)}(x)=x+n$ instead, and consider $\varphi(v)=v+1$, which is $T_{f(1)}$. The point, as above, is that $\varphi(v)\neq v$ and so also $T_{f(\varphi(v))}\neq T_{f(v)}$. Thus, there is no fixed point.

  • $\begingroup$ Reading the question strictly, $\phi$ should be among the functions $T_{f(n)}$. Of course, this is not a big issue - one solution is to let $T_{f(n)}$ compute the constant function $n+1$ instead. $\endgroup$ – François G. Dorais Mar 5 '12 at 14:51
  • $\begingroup$ Yes, I have edited. And thanks for your great answer, which gives a fuller picture of the situation in any case. $\endgroup$ – Joel David Hamkins Mar 5 '12 at 16:46
  • $\begingroup$ But does your suggestion for $T_{f(n)}$ really work? After all, if $T_{f(n)}$ is the constant $n+1$ function and $\varphi$ is one of these functions, say, constant $n+1$, then there will be $v$ with $\phi(v)=v$, namely, $v=n+1$. But then $T_{f(\phi(v))}=T_{f(v)}$. My edit makes a further change to avoid this. $\endgroup$ – Joel David Hamkins Mar 5 '12 at 16:52
  • $\begingroup$ Yes, you're right, my proposed fix wasn't fixing much! Yours is perfectly fine, of course. $\endgroup$ – François G. Dorais Mar 5 '12 at 23:32
  • $\begingroup$ This simple example answer the question. In the meanwhile, I also found a more complex example, which probably implies that the constraints $f$ needs to satisfy are quite strong. My idea is the following: consider the set of polynomial-time functions obtained through $f$ in the following way. Given a pair (i,j) $f$ returns the index of a univ TM that simulates $T_i(x)$ up to $h_j(|x|)=|x|^j+ j$ steps (0 if $T_i(x)$ does not halt). We need to recode $f$ so that it takes a single integer, but that's easy obtainable by using some bijection from $\mathbb{N}\times\mathbb{N}$ to $\mathbb{N}$. $\endgroup$ – Pietro Mar 7 '12 at 2:20

There are some very strong counterexamples to this, which illustrate the importance of so-called acceptable enumerations of partial recursive functions. Joel gave a nice one with total recursive functions, here is another striking counterexample due to Friedberg [Three theorems on recursive enumeration, JSL 23 (1953), 309-316, MR0109125].

Friedberg showed that there is a uniformly recursive one-to-one enumeration of the partial recursive functions; this is now known as a Friedberg enumeration. In other words, there is a recursive function $f$ such that every partial recursive function occurs exactly once in the listing $T_{f(0)},T_{f(1)},T_{f(2)},\ldots$. This function $f$ will necessarily fail to have fixed points.

(Unfortunately, there is no recursive enumeration of all total recursive functions at all, so there is no such strong counterexample with this added restriction.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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