# Turing machines that always halt

Needed for this paper:

Here is a possibly more clear version of my question. A Turing machine (with $$1$$ tape) has sets of tape letters $$Y$$, state letters $$Q$$, two symbols $$\alpha$$ and $$\omega$$ that mark the ends of the tape and a set of commands $$\Theta$$. A configuration is any word of the form $$\alpha uqv\omega$$ where $$u,v$$ are words in $$Y$$, $$q\in Q$$. Usually we distinguish the stop state $$q_0$$ and the input state $$q_1$$. The input configuration is any configuration of the form $$\alpha uq_1\omega$$. A command of the Turing machine is a substitution $$aqb\to a'q'b'$$ where $$a,a', b, b'$$ are either empty or letters or symbols $$\alpha,\omega$$ (with natural restriction: if, say, $$a=\alpha$$, then $$a'=\alpha$$, etc.).The command is applicable to a configuration $$\alpha uqv\omega$$ if the configuration contains a subword equal to $$aqb$$.

The machine can start working with any configuration $$\alpha u q v\omega$$. If it starts working with an input configuration $$\alpha u q_1\omega$$ and ends with a configuration containing $$q_0$$ we say that the machine accepts $$u$$.The machine can stop without accepting by arriving to a configuration where no command from $$\Theta$$ is applicable.

The language of all words accepted by a Turing machine $$M$$ is denoted by $$L(M)$$. Any recursive set $$L$$ of words is accepted by a (deterministic) Turing machine which stops on any input word (but accepts only words from $$L$$). That machine may never stop when started with some non-input configuration. For every $$L$$ it is possible to construct a Turing machine with $$L=L(M)$$ and which stops starting with every configuration (not necessarily input).

• Question: Where in the literature can I find a construction of such a Turing machine (for every recursive $$L$$)?
• I would recommend that you post this at cstheory.stackexchange.com, where there is a higher concentration of experts on that particular topic. Oct 3, 2011 at 17:05
• Short answer: I don't know. Long answer: There is a book on computability (author's name something like Hans Hermes?) which goes through various models of computability and shows their equivalence. It also has a section on Fitch's two variable model. Odds are reasonable that a book that has your model also has a citation to Hermes' book. Piergiorgio Oddifreddi also has a comprehensive intro to recursion theory. I suggest asking him or his book about where to find such a model in the classic literature. Gerhard "Ask Me About System Design" Paseman, 2011.10.03 Oct 3, 2011 at 20:29

Jean-Camille Birget answered my question. These are called universally halting Turing machines. The oldest reference is:

Martin Davis (1956). A note on universal Turing machines. In Shannon, C. E., McCarthy, J., eds, Automata Studies, pp. 167-175. Princeton University Press.

Birget proved a complexity version of this: Every deterministic Turing machine with time complexity $T(n)$ is equivalent to a deterministic Turing machine which halts after $O(T(n))$ steps, no matter what configuration of size $n$ this machine starts in [J.C. Birget, Infinite String Rewrite Systems and Complexity, J. Symbolic Computation (1998) 25, 759-793.]

Update Friedrich Otto sent the following two more references:

Herman, G.T., Strong computability and variants of the uniform halting problem, Zeitschrift fuer mathematische Logik und Grundlagen der Mathematik, 17, 1971, 115--131

Shepherdson, J.C., Machine configuration and word problems of given degree of unsolvability, Zeitschrift fuer mathematische Logik und Grundlagen der Mathematik, 11, 1965, 149--175

Note, however, that some authors use the term "mortal" differently, e.g. Hughes in "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators" uses it to mean a TM that halts on all configurations including infinite ones, and he proves that any such TM runs in $O(1)$ time, so this version of mortality is obviously too strong for most purposes.