2
$\begingroup$

I am trying to solve this problem:

Prove that there exists a partially computable function $f:\mathbb N \to \mathbb N$ that cannot be extended to a total computable function (where extension means that $g$ is total computable and $f(x)=g(x)$ for all $x$ that are not undefined).

I've tried to do the following:

Suppose that every partially computable function cam be extended to a total computable function. Take $$f(x):= \begin{cases} (\text{min t}\space STEP(x,x,t))+1, & \text{HALT(x,x)=1}, \\ \uparrow , & \text{otherwise} \end{cases}$$

STEP is the function that given the number of a program and an input, it tells if the program has already finished at step t.

Suppose there exists a total computable function $g$, with $f(x)=g(x)$ for all $x$ with $f(x) \downarrow$. I thought of this function $h$ $$h(x):= \begin{cases} 1, & f(x)=g(x), \\ 0, & \text{otherwise} \end{cases}$$

The problem is that I am not using wisely total computability of $g$ for this function, at least I cannot see how can I deduce from total computability of $g$ the total computability of $h$. Notice that $h$ is a version of the halting problem, so if I could define an $h$ similar to this one that could be deduced to be total computable using computability of $g$, then I would arrive to the wanted absurd since I already know that the halting problem can only be partially computed.

I would really appreciate if someone could help me to attack the problem with the approach I've told. All the definitions of computability and the STEP function are the ones used in the computability theory textbook by the authors Davis, Sigal and Weyuker. Thanks in advance

$\endgroup$
4
$\begingroup$

Here's the usual construction -- I guess it is just a matter of translating the very first claim into your terminology.

By the usual sort of argument from Kleene, or invoking Universal Turing machines, there is a two-place computable function $K$, such that for any total computable function $f(n)$ of one variable there is an index $e$ such that $f(n) = K(e, n)$.

Put $d(n) = K(n, n) + 1$ when $K(n, n)$ is defined, and $d(n)$ undefined otherwise. So $d(n)$ is partial computable (as I've told you how to compute it when defined!). But it is not recursively completable.

For suppose $g$ is recursive, total and completes $d$, so $g(n) = d(n)$ when the latter is defined. Then $g(n)$ is $K(k, n)$ for some index $k$. Since $g$ is total, $g(k)$, i.e. $K(k, k)$, is defined. So $d(k) = K(k, k) + 1$ is also defined. Since both are defined, $g(k)$ and $d(k)$ are equal by assumption. Whence:

$$K(k, k) = g(k) = d(k) = K(k, k) +1$$

Contradiction!

(Full disclosure: I think that argument is so cute that I couldn't resist putting it my Gödel book as Theorem 43.9 despite it being not really needed there at all!)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do you know that $d(k)$ is defined? It seems to me that it is possible that $g(k)$ is defined without $d(k)$ being defined. $\endgroup$ – orient Mar 21 '18 at 10:48
  • $\begingroup$ I've spelt out the step in the argument. $\endgroup$ – Peter Smith Mar 21 '18 at 11:36

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.