You may discuss this assignment with other students in the class, or other persons. But you must actually write the assignment in your own hand. You must turn in the homework on letter-sized paper, with your name at the top of each page. Use pen or pencil, any color.
Do not write your homework as a computer file and turn in a printout.
(a) Solvable. Emulate T for d+1 steps, where d is the size of the tape alphabet. If during that time, the machine hangs before it changes to some state other than 0, the answer is no. Else, if during that time, the machine changes to a state other than 0, the answer is yes. Else, if the machine moves either left or right, the answer is no. It will loop forever if the move is right, hang if the move is left.
The only remaining case is that the machine stays on the initial cell for the first d steps, and remains in state 0. But this computation consists of (d+2) configurations. There are only (d+1) configurations where the state is 0 and the tape is blank except for the initial cell. By the pigeonhole principle, some configuration is repeated, which implies that the machine loops forever, so the answer is no.
The problem is solvable, because we can compute the answer in finite time in every case.
(b) Unsolvable. That specific state could emulate the halt state. Thus, if the problem were solvable, the halting problem with empty input would be solvable. But the general halting problem reduces to the halting problem with empty input, because the input string could be encoded into the states. (Think of it this way: if you want to run a program with a certain file as input, and you know in advance exactly what that file is, you don't have to read it. You could just declare an array of characters and initialize the array to be the contents of the input file, then run the program as usual, emulating a read by a fetch from this array. That idea works for Turing machines, too.)
(c) Unsolvable. This reduces to the problem of determining whether, given a TM T, there exists an input string for which T halts. That is unsolvable because the problem of a TM halting with empty input reduces to it, since T can simply start by erasing all its input and then pretending it was starting with empty input.
(d) Unsolvable. Similar to (b) and (c).
(e) Unsolvable. Similar to (b), (c) and (d).
(f), (g), (h), (i), all unsolvable, same kind of logic.
(j) Solvable. M halts on every string in 10 moves or less if and only if it halts on every string of length 9 or less in 10 moves or less. The reason is that in t moves, it can read at most the first t-1 symbols of the input string.
Just emulate T on every input string of length 9 or less, and halt each emulation after at most 10 moves. Since there are only finitely many such strings, that emulation is finite. (If the input alphabet has size d, then the total number of emulated steps does not exceed 10*d^9, which is large, but finite.)
(k) Solvable. Same kind of logic as (j).
(l) Unsolvable.
The proof is by contradiction. Assume that there is machine which solves problem (l).
Suppose T is a TM and w is an input string, and you want to know whether T halts with input w, of length, say, n. We emulate T for n steps, and if it halts during that time, we have the answer. Otherwise, we do the following.
Let T_2 = T and let T_1 be a very simple TM which halts after n steps if the input is w, and never halts if the input is any other string. Then, interrogate the machine which solves problem (l). If the answer is yes, then T does not accept w, while if it is yes, T accepts w. Thus, you can solve the halting problem. Contradiction.