# Using diagonal argument to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension

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!

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

## 1 Answer

(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.

• 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. – InsigMath Mar 14 '14 at 2:39
• Are you suggesting reduction? From the halting problem? – InsigMath Mar 14 '14 at 2:40
• 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). – Yuval Filmus Mar 14 '14 at 2:53
• 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! – InsigMath Mar 14 '14 at 3:02