2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy