What is the first reference to a nondeterministic Turing machine?

Question

I am looking for the first reference of a Nondeterministic Turing machine. There is no mention of them in the 1936 paper "On Computable Numbers."

Answer 1

According to SEP, non-determinism was introduced by Rabin and Scott in Finite Automata and their Decision Problems (IBM Journal of Research and Development, 3(2) 114–125, 1959). Their main result was that it does not lead to a stronger notion of computability:

"The automata used throughout Chapter I were strictly deterministic in their tape-reading action, which was uniquely determined by the table of moves, since there was one and only one way the machine would change its state in any particular situation. Requiring all machines to be of this form can lead to rather cumbersome details, in view of the large number of internal states needed even for some relatively elementary operations. In this section we introduce the notion of a nondeterministic automaton and show that any set of tapes defined by such a machine could also be defined by an ordinary automaton. The main advantage of these machines is the small number of internal states that they require in many cases and the ease in which specific machines can be described."