Showing a function is not computable (complexity)

Question

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?

Answer 1

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.

Answer 2

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.