Nondeterminism—why did it take so long?

Michael Rabin and Dana Scott won the 1976 Turing Award. They obtained their PhD under Alonzo Church in 1957 and 1958, respectively. They are the only Turing-recognized students of Church—unless you count Alan Turing himself (1938).

Today we talk about their 1959 paper “Finite Automata and Their Decision Problems,” which was specifically cited in their award.

I believe I met each of these other famous students of Church at least once:

• Peter Andrews 1964
• Martin Davis 1950
• Stephen Kleene 1934
• Simon Kochen 1959
• Hartley Rogers 1952
• Barkley Rosser 1934
• Raymond Smullyan 1959

Of these, Peter was special to me first: I took a class from him when I was a graduate student at CMU. He was a great lecturer—I will say more about him soon.

Ken and I have just noticed while writing that Martin Davis passed away at the beginning of this month—see this memorial. We saw him and Scott speak at the 2012 Turing centennial event in Princeton.

We have mentioned Rabin and Scott together several times on this blog at least in passing, and we said more about Dana’s work in logic long ago here. Michael—I’m more used to calling him Rabin in writing—became absolutely central to computational complexity and more besides. He has won just about every award for theory, and we have discussed his work several times:

Talking About Their Paper

The Turing award citation says:

…for their joint paper “Finite Automata and Their Decision Problem,” which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field.

Whoops—are we the first to notice the typo of the missing ‘s’ from “Problems” in the paper title? It is reproduced in Wikipedia’s version. We have fingered (C)ACM editing several times recently.

Scott’s Turing Award description also says:

Computational complexity theory is the study of what is possible to calculate given a specific set of resources … Scott and Rabin’s concept of nondeterministic machines has proved extremely productive in this research area.

Yet both Rabin and Scott avoided covering the paper in their Turing Award lectures. Scott talked about his subsequent work on logics for programming. Rabin titled his talk “Complexity of Computations.” This was in accord with what he relates starting from this point of a 2015 CACM interview about his Turing Award implicitly also recognizing his 1960 paper, “Degree of Difficulty of Computing a Function and a Partial Ordering of Recursive Sets.” However, even in the expanded version of Rabin’s lecture which CACM published (searchable copy), the word “nondeterministic” is absent, and “NP” is mentioned only as part of “P = NP” twice in passing. What gives?

One look at the Rabin-Scott paper suffices to see that it lives up to the encomium of the CACM’s preface:

[It] has become a classic paper in formal language theory that still forms one of the best introductions to the area. The paper is simultaneously a survey and a research article; it is technically simple and mathematically impeccable.

The ‘survey’ aspect is that the paper includes, organizes, and polishes equally famous work by Kleene, John Myhill, and Anil Nerode, plus building on papers by Edward Moore, Arthur Burks and Hao Wang, and (with mutual rounds of interchange) John Shepherdson. The final paper—including the results original to Rabin and Scott—reads like how we teach the automata section of an intro theory course today. The seminal original result to teach is their powerset construction converting an NFA into an equivalent DFA. Yet some elements are missing, and they may be key to why nondeterminism took so long to formulate.

Time Lapse and a Missing Link?

The introduction of nondeterministic machines is often dated to Rabin-Scott in 1959. Yet Kleene’s famous theorem converting deterministic finite automata (DFAs) into what he termed regular “events” dates to 1951. Their equivalence naturally goes through nondeterministic finite automata (NFAs). Were NFAs really unknown to Kleene? Moreover, notions of existentially quantified predicates equivalent to nodeterminism go back even before Turing, as noted in this StackExchange query on “Who introduced nondeterministic computation?”

Some of this apparent 8-year gap is closed by a footnote on the first page of Rabin-Scott:

“The bulk of this work was done while the authors were associated with the IBM Research Center during the summer of 1957.”

That shaves off two years. Five more may owe to Kleene’s report not appearing in final journal form until 1956, when the notation for what he now termed regular expressions was more polished. But this version still gives nothing near the “” style of notation which is inchoate in Rabin-Scott. Kleene’s graphical diagrams are of nerve nets, as defined in 1944 by Warren McCullogh and Walter Pitts, not state graphs as we represent them now.

I—Ken writing these sections—still wonder why NFAs were not defined earlier. Current renditions of Kleene’s Theorem do not care whether a DFA or NFA is given. I speculate the reason is that the most elegant association of NFAs to regular expressions requires what was literally a missing link:

Here stands for the empty string. Thus the arc represents a change of state without stimulus, an idea that is antithetical to nerve nets. I still imagine an alternate history where someone like Charles Peirce, whose electrical diagrams of Boolean logic we noted here, conceived a century earlier of representing the laws of electric circuits symbolically like so:

When the conversion from regular expressions to NFAs was published by Robert McNaughton and Hisao Yamada in 1960, they conditioned their regular expressions into a form that avoided occurrences of . Using for this conversion has been traced back only to Ken Thompson in 1968. That was only a few years before I met this future Turing laureate at the Westfield Chess Club.

In my alternate history, nondeterminism would have seemed natural from forking electrical flow. Instead, as Rabin relates at this point in his 2015 interview, he and Scott felt they needed to start from a limited form of a Turing machine, the full model then seeming unapproachable.

“So we had the model of what are called finite automata and then we decided, as pure exercises for imagination, to consider all possible variations. One of those variations was nondeterministic automata.”

Their other variations allowed two-way heads or multiple tapes. In my telling, nondeterminism might have been regarded not as a “variation” but as more fundamental than determinism. Going back to Rabin-Scott and forward again to Thompson and his co-workers at Bell Labs, this is what I argue next.

Nondeterminism is Fundamental

A text by John Martin makes the joke that understanding tuple notation like “” is a sign of being a mathematician. I turn it around and say it’s really a sign of being an object-oriented programmer:


class FA {
   set<State> Q;
   set<char> Sigma;
   State s;
   set<State> F;
   ...
}


I continue by saying that if you were to define as a method via State delta(State q, char c) then you would be stuck with the same method body for each machine instance. This issue can be fixed by making delta a function pointer (or “delegate” in terms of the programming language C#), but I hold it more natural to make delta a set of triples of type (State,char,State) instead, which I call instructions. This notation naturally defines an NFA. Then the machine is deterministic (i.e., a DFA) when for all states and characters there is exactly one such that is an instruction. I then ask the students,

Which is the base class, DFA or NFA?

Insofar as automata once created are immutable, the answer is NFA: A DFA “Is-A” NFA that obeys the logical constraint on the set of instructions. In this rendition, NFA is the simpler and more fundamental concept. It remains so after allowing triples of type (State,ε,State) too.

Later in the course I plump nondeterminism over determinism in other ways:

• The widest expanse of interesting computational problems are complete in NP, not in P.
• Many of the problems we put into P—including some decision problems in the Rabin-Scott paper—are really complete for nondeterministic logspace.
• The canonical simulation via breadth-first search goes from nondeterministic space to deterministic time, and depth-first search takes one from nondeterministic time to deterministic space. Nondeterministic machines are the necessary givens.
• Nondeterministic/existential forms of classes often have more characterizations and closure properties.
• Hadamard gates are nondeterministic; quantum circuits using only Pauli and permutation gates (CNOT, Toffoli, …) can do classical logic only.

But the main point I make right away is about succinctness: NFAs are not only usually smaller and more readable than their equivalent DFAs, they are often more workable. To exemplify this, I offer two ways of deciding whether a given string matches a given regular expression : After converting into an equivalent NFA via Thompson’s algorithm diagrammed above, one can either

1. Convert into an equivalent DFA and simply run on ; or
2. Simulate on by updating the set of possible states before is read to after is “processed,” as in the guts of the proof of the Rabin-Scott construction.

I give the examples , which denotes binary strings whose -th bit from the end is a . Ways I show of economizing on -arcs yield an NFA with just states. Whereas, the smallest DFA such that has states—as we prove via Myhill and Nerode’s theorems (using the latter as given in the survey part of Rabin-Scott).

Thus, method 1 involves exponential time in worst case, while method 2 works in time polynomial in and . Method 2 is essentially the algorithm designed by Thompson and co-workers. This is the first example in the course of the contrast between exponential and polynomial times for the same problem. I show how the NFAs capture the logic of the problem, whereas the DFAs look like a twisty mess even for . Showing a diagram of or a partial sketch of , I ask:

Would nature ever do this?

This aims to say: the NFA is often more real than the equivalent DFA.

Open Problems

Would Rabin or Scott go this far? We could ask them… We note, however, that the word “deterministic”—to say nothing of “nondeterministic” and their other word forms—is absent from this wonderful list of quotes from Rabin’s classes, including:

• This is trivial, but not obvious. (Fall 1996)
• If P = NP, then all of modern cryptography collapses. On this happy thought… (Fall 1998)
• Zero plus zero is still zero, even in this advanced class. (Spring 2002)
• It is customary for a student and teacher to be on first name basis once the student gets his Ph.D. Personally I found it difficult to address Church as “Alonzo”, but I managed. So let us do it. (Spring 2008)

We have been talking about people over age 90 and this is true of both Rabin and Scott—and Nerode. We wish them sto lat—but at this point, could that traditional long-life wish be an underestimate?