# How to prove that there is a function index t so that t³ + t + 1 is an index of the same function?

I would like to prove $\exists t\phi_t = \phi_{t^3+t+1}$ where $\phi_0,\phi_1,\phi_2,...$ are sequence of all of the partially computable function.

$\phi_t = \phi_{t^3+t+1}$ only if $t = t^3+t+1$ and it means $t=-1$! and there is no program with number $-1$!

• Your remark in incorrect. A partially computable function can have many Gödel numbers, so that $\phi_u=\phi_v$ is possible even when $u\neq v$. Hence you cannot infer here that $t = t^3+t+1$ from $\phi_t = \phi_{t^3+t+1}$. Mar 1 '15 at 17:28
• I was searching on internet, I came across Padding Lemma which says every computable function has infinite indices. So is this lemma a contradiction to my reasoning? Mar 1 '15 at 17:35
• Important requirement: $\phi$ is a Gödel enumeration. This does not work for all enumerations.
– Raphael
Mar 1 '15 at 23:57
• @Raphael fixed point theorem says there are infinitely many $e$ such that $\phi_{f(e)} = \phi_e(x)$ , why it doesn't work for all enumerations? Mar 2 '15 at 9:09
• @user2851298 The FPT only holds for Gödel enumerations. The WP article is not very clear about that, but then most articles there about recursion theory are horrible. (Also, not all variants of the FPT say that there are infinitely many such indices. Make sure you are allowed to use one that is powerful enough.)
– Raphael
Mar 2 '15 at 11:25

This is just a special case of Rogers' fixed-point theorem which says that, for any total computable function $f$, there exists $t$ such that $\phi_t = \phi_{f(t)}$.
• In fixed point theorem the $e$ is constant while in here $t$ is variable not a constant value. Mar 1 '15 at 18:16
• @user2851298 It doesn't matter whether you call the index $t$ or $e$. Mar 1 '15 at 20:05