The halting problem for tapes that are or are not completely blank

Question

Is it possible to construct a Turing machine that halts only if the tape is not completely blank? Also, is it possible to construct one to halt if the tape is completely blank?

Intuitively, I think the answer to the first question should be that it is possible to construct a machine that halts if the tape is not completely blank. However, I don't know how to go about doing this. Because if we assume that we start at a random location on the tape, we have to search in both directions to find a stroke and then halt there. Is there something equivalent to an NFA using Turing machines, so that we can search in both directions simultaneously?

For the second question, I think the answer is that it's not possible because we can search infinitely in both directions without every coming upon a stroke.

Answer 1

You are correct. Here is an informal proof:

For the first, let $t_i$ represent the tape, with $i \in \mathbb{Z}$.

1. If any of $t_{-1},t_0,t_1$ are not blank then halt. Return to position $0$ and mark $t_0$.
2. Move right until $t_i$ is blank. If $t_{i+1}$ is not blank then halt, otherwise return to position $i$ and mark $t_i$.
3. Move left until $t_i$ is blank. If $t_{i-1}$ is not blank then halt, otherwise return to position $i$ and mark $t_i$.
4. Goto Step 2.

Here is a rough description: $b$ means a blank tape symbol, $x$ means any symbol (and write the same symbol). For a given state, the first line has precedence over subsequent lines, so, for example, in state $7$, a blank symbol means go to state 8, and any other input results in a halt. The $*$ on the last line defines all transitions not previously specified.

\begin{array}[cccc] & \text{state} & \text{symbol} & \text{next state} & \text{new symbol} & \text{move} \\ 0 & x & 1 & x & L \\ 1 & b & 2 & b & R \\ 2 & b & 3 & b & R \\ 3 & b & 4 & b & L \\ 4 & x & 5 & 1 & L \\ 5 & x & 6 & x & R \\ \\ 6 & 1 & 6 & 1 & R \\ 6 & b & 7 & b & R \\ \\ 7 & b & 8 & b & L \\ 7 & x & \text{halt} & - & - \\ 8 & x & 9 & 1 & L \\ \\ 9 & 1 & 9 & 1 & L \\ 9 & b & 10 & b & L \\ 10 & b & 11 & b & R \\ 10 & x & \text{halt} & - & - \\ 11 & x & 6 & 1 & R \\ \\ * & x & \text{halt} & - & - \\ \end{array}

For the second, suppose the machine halts after $n$ steps on a blank tape. Then construct a tape such that $t_i$ is blank for $|i| \le n+1$. Then the machine will halt on this tape, since the head can only move one step at a time and in $n$ steps, it can only encounter blank tape. Consequently, the machine cannot discriminate between this tape and a blank tape.

Answer 2

Basically, you're right. Below is what I think; it's largely a restatement of what you wrote.

Is it possible to construct a turing machine that halts only if the tape is not completely blank?

Yes. Let there be a turing machine $T$ that reads an input tape $M$ and halts on the first non-blank input it encounters. (There are many constructions you can make to have the head of $T$ travel in 'both directions' on $M$.)

Is it possible to construct a turing machine that halts only if the tape is completely blank?

No. There is no way to tell if the tape is completely blank, because we assume that the tape extends to infinity in both directions. So the Turing Machine will read the tape forever.