3
$\begingroup$

A partial computable function is also known as effectively computable, and is defined as any function that can be computed by a Turing machine with $Dom(f) \subseteq \Sigma^*$, where $\Sigma^*$ is the Kleene star of the alphabet $\Sigma$ for the Turing machine that satisfies partial computability.

How do we know that there exists a function from $\mathbb{N}$ to $\mathbb{N}$ that is not partial computable?

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ Hint: how many functions from $\mathbb{N}$ to $\mathbb{N}$ are there? $\endgroup$ – Ross Millikan Apr 27 '11 at 13:41
  • 3
    $\begingroup$ Hmm... I'm going to guess uncountably many? Because there are countably many Turing machines, then that implies there must exist some function from $\mathbb{N}$ to $\mathbb{N}$ that cannot be represented by a Turing machine. $\endgroup$ – Rob Apr 27 '11 at 13:53
  • 1
    $\begingroup$ You got it. One proof that there are uncountably many: Think of the set of functions that for each $k \in \mathbb{N}$ either take $2k$ to $2k$ and $2k+1$ to $2k+1$ or interchange them ($2k$ to $2k+1$ and $2k+1$ to $2k$). There is a bijection of this set of functions with binary bit strings (interchange at $k$ if there is a $1$ bit at position $k$) $\endgroup$ – Ross Millikan Apr 27 '11 at 14:17
  • $\begingroup$ you could write up an answer so this doesn't keep coming back (the robot on the site returns unanswered questions periodically) $\endgroup$ – Ross Millikan Apr 27 '11 at 14:22
  • $\begingroup$ @Ross. Thanks, I will do that. $\endgroup$ – Rob Apr 27 '11 at 20:56
6
$\begingroup$

The counting argument is very beautiful but you should also know Alan Turing's demonstration,

According to set theory every Turing machine either halts or does not halt, so let us encode Turing machines as natural numbers and write a map from them to "1" if they halt and "0" if they do not.

That function $\text{halts} : \mathbb N \to \mathbb N$ cannot be implemented in a Turing machine, if it were then you could also build a Turing machine that uses it as a subroutine for the following

natural liar(natural t) { if(halts(t)) { loop(); } else { return 0; } }

This Turing machine takes a Turing machine encoded as a number and loops if it halts and halts if it loops! When you apply this Turing machine to the number encoding it's self you get a paradox, which contradicts the possibility of the "halts" function being implemented in a Turing machine.

Improve this answer
$\endgroup$
0
3
$\begingroup$

A pure "counting" argument, as in the comments, does the job. But perhaps it is worthwhile to be more explicit.

There are countably many Turing machines, so they may be enumerated as $T_0$, $T_1$, $T_2$, and so on.

Let $f(e,x)=0$ if the Turing machine $T_e$ does not halt on numerical input $x$, and let $f(e,x)$ be $1$ more than the result of applying $T_e$ to $x$ otherwise. Finally, let $g(x)=f(x,x)+17$.

We show that $g$ is not Turing computable. For if it is, there is a Turing machine $T_a$ such that $f(a,x)=g(x)$ for all $x$. Put $x=a$. We find that $f(a,a)=g(a)$. But $g(a)=f(a,a)+17$, so $17=0$.

In a way, the above argument is implicit in the "counting" argument, since one shows that the set of functions from $\mathbb{N}$ to $\mathbb{N}$ is uncountable in precisely this way. But it is worthwhile to be explicit, as an easy prelude to more subtle but similar arguments.

Improve this answer
$\endgroup$

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.