# 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. – Jacques Carette Oct 3 '11 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 – Gerhard Paseman Oct 3 '11 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.