1
$\begingroup$

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$!

$\endgroup$
5
  • 4
    $\begingroup$ 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}$. $\endgroup$
    – babou
    Mar 1 '15 at 17:28
  • $\begingroup$ 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? $\endgroup$ Mar 1 '15 at 17:35
  • 1
    $\begingroup$ Important requirement: $\phi$ is a Gödel enumeration. This does not work for all enumerations. $\endgroup$
    – Raphael
    Mar 1 '15 at 23:57
  • $\begingroup$ @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? $\endgroup$ Mar 2 '15 at 9:09
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Raphael
    Mar 2 '15 at 11:25
5
$\begingroup$

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)}$.

$\endgroup$
3
  • $\begingroup$ In fixed point theorem the $e$ is constant while in here $t$ is variable not a constant value. $\endgroup$ Mar 1 '15 at 18:16
  • $\begingroup$ @user2851298 The fixed point is the function, not the subscript. $\endgroup$ Mar 1 '15 at 19:37
  • 1
    $\begingroup$ @user2851298 It doesn't matter whether you call the index $t$ or $e$. $\endgroup$ Mar 1 '15 at 20:05

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.