# Example of non extensible functions ( $f(x) \notin EXT$) for reduction

This is the definition of $EXT = \{x\ | \varphi_x\ can\ be\ extended\ to\ a\ total\ computable\ function \}$. I'm trying to proof that $\overline{K} \le_{rec} EXP$ and I can't think of an example of a function that can't be extended

A classic example is

$$f(n) = \begin{cases} k & \mbox{if \phi_n(n)\downarrow in exactly k steps} \\ \uparrow & \mbox{if \phi_n(n)\uparrow } \\ \end{cases}$$

Above, "in $k$ steps" can be formalized more precisely using TMs (or another equivalent computational model), or Kleene's T,U normal form.

Here $f$ is trivially computable: we can try to simulate the evaluation of $\phi_n(n)$ using a universal program / TM / whatever, and count the number of required computation steps.

Further, $f$ is partial since its domain is $K$.

However, $f$ can not be extended to a total recursive function $g$, since otherwise we could exploit $g$ to decide $K$. Indeed, $n\in K$ is equivalent to "$\phi_n(n)$ converges in $g(n)$ steps", and the latter is decidable if $g$ is total recursive.

Every total uncomputable function cannot be extended to a total computable function. More generally, let $g$ be an uncomputable function, and let $h$ be a total computable one-to-one function, for example $h(x) = 2x$. Define a partial function $f$ by $f(h(x)) = g(x)$ (so $f$ is defined only on the range of $h$). The function $f$ cannot be extended to a total computable function.

• With "uncomputable" you mean that the function diverges on every input? – user43288 Feb 12 '18 at 15:25
• @GerardoZinno "uncomputable" simply means "not computable". Above it is also taken to be total, so it never diverges. – chi Feb 12 '18 at 17:42