Hello everyone just like the title says I want to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension such that if we had a function $BIG(x)$ that is both total and agrees with $H(x)$ whenever $H(x)$ is defined, then $BIG(x)$ is not computable. This is a homework question so I don't want a full solution just some help!

$\bf{NOTE}:$ The predicate $T(y,x,z)$ means that it holds iff program $y$ takes an input $x$ (could be $n$-ary) and has a computational history z! This is supposed to be the Kleene T predicate basically.

The function $H(x)$ I believe returns the smallest computational history $y$ such that a program $\{x\}(x)$ (program takes input of its own configuration and runs) runs and halts, since $\mu y R(x,y)$ means the smallest $y$ such that $R(x,y)$ holds. Maybe I am not quite clear what it means for $BIG$ to agree with $H(x)$ or what it's own input. I think I need to create a diagonal function that uses $BIG$ if $BIG$ was computable and show that if I had some program $e$ then it must agree with $BIG$ but based on my definition of that diagonal function it isn't. If you are reading this you might see the mess of my thinking, any help would be greatly appreciated!

  • $\begingroup$ The z us actually supposed to be the computational history which can be represented by the Gödel numbering system $\endgroup$ – InsigMath Mar 14 '14 at 2:35
  • $\begingroup$ You should add this information to the question. Different people have different notation and terminology. $\endgroup$ – Yuval Filmus Mar 14 '14 at 2:54

(This answer assumes my conjectural interpretation of the predicate $T$.) The function $H(x)$ is given by $$ H(x) = \begin{cases} t & \text{if program $x$ run on input $x$ halts after $t$ steps} \\ \bot & \text{if program $x$ never halts when run on input $x$} \end{cases} $$

Hint: Given a total computable function extending $H$, show how to solve the halting problem. There is no need to use diagonalization – this is already taken care of in the proof that the halting problem is undecidable.

  • $\begingroup$ The T predicate is the kleebe predicate which is the n+2 ary predicate that takes a program z with n-ary input x and the computational history z and returns true or false if the program halts on that input with that computational hiatory. I am not sure if that changes your comment though. $\endgroup$ – InsigMath Mar 14 '14 at 2:39
  • $\begingroup$ Are you suggesting reduction? From the halting problem? $\endgroup$ – InsigMath Mar 14 '14 at 2:40
  • $\begingroup$ My argument works also for your definition of $T$, and in any case that doesn't make a huge difference. I'm not suggesting a many-one reduction but a Turing reduction. The name doesn't matter – I suggest that you show that given a total computable function extending $H$, you are able to solve the halting problem (for a program $x$ getting itself as an input). $\endgroup$ – Yuval Filmus Mar 14 '14 at 2:53
  • $\begingroup$ Thank you, I will think about how to solve it this way, although the problem is we are asked in this question to use a diagonal argument, and in this particular course our medium of computation is register machines not turing machines, but I always look forward to thinking of multiple methods even if I cannot use it for my solution! $\endgroup$ – InsigMath Mar 14 '14 at 3:02

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.