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