0

Let f be a function that for a given (TM encoding) returns the rightmost cell visited by M when running on epsilon, f will return infinity if there's no such index.

I need to show that f is not computable.

If f would have been computable, it could be used to decide the Halting problem and so on, is it enough to proof that?

Gabriel 1993
  • 3
  • Yes, if you can prove that a computable f would solve the halting problem you are done. We know the halting problem is unsolvable. That is one of the main techniques for proving something uncomputable. – Ross Millikan Jun 19 '17 at 20:15
  • @Gabriel1993 Do you already have an idea about how to prove that the computability of $f$ would imply the computability of the Halting problem? – Erick Wong Jun 19 '17 at 20:27
  • @ErickWong I'll manage, thanks. – Gabriel 1993 Jun 19 '17 at 20:31

2 Answers2

1

Yes, that's enough. This technique is called Reductio ad absurdum. Basically, you assume $f$ is computable and reach a contradiction (because we know the Halting Problem is not solveable). Therefore, the assumption that $f$ is computable must be wrong, so $f$ must be non-computable.

Glorfindel
  • 3,955
0

In the following I will assume that the tape of a Turing machine is infinite to the right but has a leftmost tape cell.

$f$ is given by

$$f(\langle M \rangle) = \begin{cases} k & \text{if the rightmost tape cell visited by Turing machine $M$ on input $\varepsilon$ is cell no. $k$} \\ \\\text{$\infty$} & \text{if $M$ visits all cells on input $\varepsilon$ } \end{cases}$$

Suppose $f$ were Turing-computable. Then the halting problem

Given TM $M$ and input $w$, will $M$ halt on input $w$?

would be decidable using the following decider

On input $\langle M,w\rangle$

  1. Build $\langle M' \rangle$, which is the description of a Turing machine that ignores its input and simulates $M$ on input $\varepsilon$
  2. Compute $f(\langle M' \rangle)$
  3. If $f(\langle M' \rangle) = \infty$, then reject
  4. Else, if $f(\langle M' \rangle) = k$, then simulate $M'$ on input $\varepsilon$ until some configuration of $M'$ is repeated or $M'$ halts
  5. If a configuration was repeated, then reject, else accept

In the above decider, we make use of the fact that if $M'$ never visits a tape cell beyond cell no. $k$, then $M'$ can only enter an infinite loop if some configuration in the computation is repeated, since there are only finitely many machine configurations whose tape part has length at most $k$.

If we instead assume a doubly infinite tape, the construction can be easily modified by constructing the "mirror image" $M^R$ of $M$ that moves left whenever $M$ moves right and vice Verda. We then check if we have both $f(M^R)$ and $f(M)$ finite, in which case we simulate $M$ or if at least one of the two values is infinite, in which case $M$ will not halt.

Hans Hüttel
  • 4,271
  • This is the right idea, but missing one detail: a Turing machine has a bidirectional infinite tape, so it's possible for it not to visit every cell on the right, but wander infinitely towards the left without ever repeating. This is easily repaired by constructing the mirror image TM which behaves identically to $M$ but flips left and right directions. – Erick Wong Jun 20 '17 at 02:53
  • 1
    It is not necessarily the case that the tape is infinite to the left – in many textbooks (such as Sipser's textbook( this is in fact not the case. – Hans Hüttel Jun 20 '17 at 02:56
  • Interesting. In that case it would be good to get clarification on which definition is being used here, though the asymmetry in the question weakly hints that it is indeed a one-sided infinite tape. – Erick Wong Jun 20 '17 at 03:02