Example of a partial computable function that cannot be extended to a total computable function

Question

Today in my Computability Theory class the professor introduced the following non-recursive class: $$EXT = \{x : \varphi_x \text{ can be extended to a total computable function}\}$$

(Where by $\varphi_i$ I indicate the $i$-th computable function)

He didn’t really give a definition of “extending a function to a total function”, but what I got through context was the following:

$$ x \in EXT \iff \exists \text { total } \bar\varphi_x . (\forall n \in \text{dom}(\varphi_x). \varphi_x = \bar\varphi_x) $$ The fact that I might have got the definition wrong may be among the causes of my confusion;

Later (after the end of the lesson), the professor was asked by a student to prove a statement regarding $EXT$, but could not think of an example of a partial computable function that cannot be extended to a total computable function. Another student suggested the following: $$ \psi (x) = \begin{cases} n, & \text{if $\varphi_x(x)$ converges in $n$ steps;} \\ \text{undefined,} & \text{otherwise.} \end{cases} $$

Saying that replacing the undefined with any natural number would result in a contradiction, and the professor seemed to agree.

My question actually consists of two parts I guess:

• What is the correct definition?
• Is that example a valid example?

EDIT: fixed my intuitive definition, twice

Answer 1

In general, consider sets $A, B$ and functions $f : S \to B$, $g : R \to B$ where $S, R \subseteq A$. Equivalently, $f$ and $g$ are partial functions $A \to B$. Then we say “$g$ extends $f$” if and only if $S \subseteq R$ and $\forall s \in S (f(s) = g(s))$.

In this context, we have a partial recursive function - that is, a recursive function $f : S \to \mathbb{N}$ where $S \subseteq \mathbb{N}$. We are asking whether there is any total recursive function $g : \mathbb{N} \to \mathbb{N}$ such that $\forall s \in S (g(s) = f(s))$.

The example your classmate provided is valid. For let us suppose $\psi$ extends to a total recursive function $\theta : \mathbb{N} \to \mathbb{N}$. Then I claim that the set $\{x \in \mathbb{N} \mid \phi_x(x)$ is defined $\}$ is recursively decidable.

For if we wish to decide whether $\phi_x(x)$ is defined, we first compute $\theta(x)$. We then see whether the computation of $\phi_x(x)$ halts in exactly $\theta(x)$ steps. If so, then clearly $\phi_x(x)$ is defined. If not, then suppose $\phi_x(x)$ were defined; then the computation of $\phi_x(x)$ would halt in $n$ steps for some $n$. That is, $\psi(x) = n$. Since $\psi(x)$ is defined, $\psi(x) = \theta(x)$. So we would have that $\phi_x(x)$ takes exactly $\theta(x)$ steps to compute.

But it is well-known that $\{x \mid \phi_x(x)$ is defined$\}$ cannot be recursively decidable. Therefore, $\psi$ can’t be extended.