The uniform halting problem for generalized one state turing machines

Abstract

The uniform halting problem (UH) can be stated as follows: Give a decision procedure which for any given Turing machine (TM) will decide whether or not it has an immortal instantaneous description (ID). An ID is called immortal if it has no terminal successor. As it is generally the case in the literature (see e.g. Minsky p. 118) we assume that in an ID the tape must be blank except for some finite number of squares. If we remove this restriction the UH becomes the immortality problem (IP). The unsolvability of the IP was shown by Hooper. It can be seen from Part V (p. 225) of his paper that his method also shows the unsolvability of the UH. The initialised UH, whether or not a TM has an immortal ID when started in a specified state, is also known to be undecidable. (See e.g. Minsky p. 151). For one state TM's the two problems are of course equivalent. Hooper (Part VI, 5) found that the IP is solvable for two state TM's. However, one can show (Herman) that the UH (just like the halting problem) is unsolvable for two state TM's. The halting problem is known to be solvable for one state TM's, even if we allow them to have a many dimensional tape (see Herman). Can the same be said about the UH? In this paper we show the solvability of the UH for one state TM's. These are not entirely trivial structures, they can do, as we show, certain things that finite automata cannot do. We consider in what ways we can generalise one state TM's so that we retain the solvability of the UH. We find that the UH for one state TM's with two dimensional tape and jumping reading head (i.e. the reading head can move to squares not immediately neighbouring the previously scanned square) is also solvable. Our method does not generalize for three or more dimensional tape, unless we put in some conditions on the directions in which the reading head can move. On the other hand, we find that one state TM's with two or more tapes or with two or more reading heads on the same tape have an unsolvable UH. Finally we consider how a different choice of formalism would influence our results.