Turing machines that always halt

Question

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$)?

Answer 1

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

Answer 2

[I know this has already been answered satisfactorily, but for the sake of future readers, here's some additional terminology and an additional reference.]

These are also known as mortal Turing machines. See, e.g., this answer. Also discussed in

Hooper, P. K. The Undecidability of the Turing Machine Immortality Problem. J. Symb. Logic, 1966.

The key to the proof in the above paper is avoiding infinite loops starting from unreachable (finite) configurations, which is the same as the key to the construction alluded to in the question.

(This paper also contains the great line: "Most of the detailed work has been banished to the Appendices, to give the casual reader an opportunity to sample the flavor of the construction without choking on its bones.")

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.