Decidability: Answers
  1. This problem is decidable. As T proceeds in its computation, one of the following must eventually occur:

    2.  
    1. T changes state
    2. T crashes without having changed state
    3. T moves its tape head to the right without having changed state
    4. without having changed state, T writes a symbol on square 0 that it has previously written
    In the first two cases, we have the answer to the question. In either of the last two cases, T must be in an infinite loop, and thus we may answer the questions negatively.
     
  2. This problem is undecidable. To show this is the case, we reduce the problem of whether or not a Turing machine accepts the empty string (which is known to be undecidable) to it. Given a TM T, we construct a TM T' which has all the states in T plus an additional one, called q. T' works by making exactly the same moves as T, except that if T ever halts, T' moves instead to state q, then halts on the next move. Clearly T accepts the empty string if and only if T' enters state q.

    3.  
  3. This problem is undecidable. We can use exactly the same construction as in the previous question to show that this is the case.

    4.  
  4. This problem is undecidable. To show this is the case, we reduce the problem of whether or not a Turing machine accepts the empty string (which is known to be undecidable) to it. Given a TM T, we construct a TM T' which has all the states in T plus an additional one, called q, and all of the symbols of T, plus an additional one, $. For any move that would cause T to halt, T' instead moves to the start state of T and places $ on the tape. Thereafter, the $ causes T' to cycle through all its non-halting states, q being the last, before halting. On the one hand, if T accepts the empty string, then some move causes T to halt, and therefore T' enters all its non-halting states when started with a blank tape. If T does not accept the empty string, then since T never executes a halting move after starting with a blank tape, T' will never enter state q, and so does not enter all its non-halting states.

    5.  
  5. This problem is undecidable. We can use exactly the same construction as in the previous question to show that this is the case.

    6.  
  6. This problem is undecidable. To show this is the case, we reduce the halting problem (which is known to be undecidable) to it. Given a TM T, we construct a TM T' which copies T but also keeps track of whether it has made an even number of moves or an odd number. The other difference between T and T' is that if T halts after an odd number of moves, then T' makes an additional move before halting. The result is that T' accepts exactly the same strings as T, but halts only after an even number of moves. Therefore, T halts if and only if T' halts after an even number of moves.

    7.  
  7. This problem is undecidable. We can use exactly the same construction as in the previous question to show that this is the case.

    8.  
  8. This problem is undecidable. To show this is the case, we reduce the problem of whether or not a given Turing machine halts over a given string (which is known to be undecidable) to it. Given a TM T, we construct a TM T' that accepts the same language but never crashes. Then for any input string w, T fails to accept w if and only if T' loops forever on w. This means that the problem of whether or not a given Turing machine halts over a given string is reducible to this one.

    9.  
  9. This problem is undecidable. We can use exactly the same construction as in the previous question to show that this is the case.

    10.  
  10. This problem is decidable. The reason is that within 10 moves, a TM cannot move its tape head any further right than square 10. Therefore, if necessary, we can look at the first 10 moves T makes for every possible input string of length 10 or less. At the end of this process, we will know whether T halts within 10 moves on every string.