2
$\begingroup$

The problem of deciding, for any $x$, whether $\phi_x$ is a constant function, is undecidable. I came across the following proof of this fact in Rogers' book:

enter image description here

To me, it looks too bulky and unnecessarily complicated (things like the unnecessary (I think) use of the S-m-n theorem, the introduction of this weird function $gh_1$...). I think if one uses the existence of a Gödel universal function, it makes the proof much more clear (and shorter). Namely, define the partial function $V:N\times N\to N$ by (see the definition of $K$ below) $$(q,x)\mapsto 1 \text{ if $q\in K$} \\ (q,x) \text{ is undefined if $q\notin K$}$$ This is a computable function by the Church-Turing thesis (a program that computes it would accept a pair $(q,x)$ (if this pair is coded as one number, it would decode it), run $\phi_q(q)$; if it stops, the output would be one; if not, then it would run forever). Now let $U$ be a Gödel universal function. Then there exists a total computable $s:N\to N$ such that for all $q,t\in N$, $$V(q,t)=U(s(q),t).$$ Now $K=\{q:\phi_q(q)\text{ halts}\}$ is $m$-reduced to $\{x:\phi_x\text{ is constant}\}$ via $s$. Thus the latter set is unsolvable.

If this proof is correct (is it?), it makes me wonder if one can forget about the S-m-n theorem and only remember the existence of Gödel universal functions. Is it some kind of archaic result? Another thing that make me think this way is that there exist textbooks in recursion theory (more modern than Rogers' book) which do not make any explicit mention of this S-m-n theorem, but they use these Gödel universal functions quite a bit (Rogers doesn't explicitly mention them, I believe).

$\endgroup$
  • 1
    $\begingroup$ Godel universal function and s-m-n look like basically the same thing to me. The $h_1$ is your $s$, the $\psi$ is your $V$, and the $\varphi$ is your $U$. $\endgroup$ – Ted May 27 at 2:54

Your Answer

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

Browse other questions tagged or ask your own question.