What publication first introduced the concept of a non-deterministic Turing machine?

Turing did not define the concept in his 1936 paper.


1 Answer 1


This will be a partially inconclusive answer, unfortunately. Hopefully someone more knowledgeable can chime in and confirm the missing details. Let me summarize what I could find out so far.

Nondeterministic automata were introduced by Rabin and Scott in 1959. They also define two-way automata (which is a prelude to the LBAs introduced by Myhill the following year), but I could not find any mention of a nondeterministic two-way automaton (let alone a Turing machine) there.

The next paper (in chronological order) in which both nondeterminism and Turing machines appear is "On computability by certain classes of restricted Turing machines" by Fischer, 1963. In it, he defines general machines and also allow them to be nondeterministic. However, in the proof of Theorem 5 there he curiously states that some results (regarding deterministic and nondeterministic machines) are "well-known" to be equivalent for Turing machines. Hence, one is lead to believe the notion must have arisen sometime between the Rabin and Scott paper and Fischer's paper in 1963. Fortunately, Fischer gives a clue as to where he has those results from:

The author is indebted to Dr. J. Evey for many of the ideas contained herein. He has worked closely with the author in this area and, in particular, is responsible for the results constituting parts (c) and (d) of Theorem 3 and for the main construction in part (e).

Theorem 3 in case is the computational equivalence of DTMs and NTMs.

Indeed, roughly a month after Fischer's paper Evey published "Application of pushdown-store machines," in which we also find nondeterminism applied to general machines (including Turing machines), and in which he proves the result that Fischer mentions (and extending it to some other types of machines). Fischer's work is actually listed in the bibliography there as well, but as far as I can tell there is no explicit citation of it in the text. The paper is most likely a summary of Evey's doctoral thesis (similarly titled), but I could not find it online; maybe someone with access to it can confirm that.

What I conclude then is that, unless I have made a gross oversight somewhere, the notion of an NTM must have just been evident to the research community once Rabin and Scott had brought nondeterminism to the table. Evey deserves credit for proving the computational equivalence of DTMs and NTMs, but it is hard to tell from the evidence at hand if he was the first to mention NTMs as a concept too (possibly in his doctoral thesis).

  • $\begingroup$ It may be inclusive, but it's deeply appreciated. Thank you so much for the precise references. $\endgroup$
    – R. Chopin
    Aug 23, 2019 at 17:32
  • $\begingroup$ Glad to be of help. Going after stuff like this is always good practice in "unearthing" papers—especially when you need to travel over 50 years back in time to do so :) $\endgroup$
    – dkaeae
    Aug 23, 2019 at 18:13
  • $\begingroup$ Indeed. And that's true scholarship --- taking stock of the past ---, which, in a sense, is more important than taking it forward. $\endgroup$
    – R. Chopin
    Aug 23, 2019 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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