MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$)?
share|cite|improve this question
I would recommend that you post this at, 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
up vote 8 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.