Doing everything all at once, or magically making the right choices.

How to drive anywhere

Need directions for driving from Albuquerque to Toronto? It’s very easy, just three simple steps:

When you come to a street, drive down it to the next intersection.
When you come to an intersection, take one of the roads leading out of the intersection.
When you reach your final destination, stop.

The beauty of these directions is they also work for driving from Johannesburg to Accra, or between any other two destinations connected by roads.

“‍But,‍” I seem to hear you say, “‍the second step isn’t complete. Which way should I turn?‍” The answer: choose all of the options nondeterministically. When you come to a four-way intersection, split the universe into four alternate universes, one where you take each of the four possible options. The next intersection will split each of those universes further, until one of them reaches the destination. As soon as that happens, just get rid of all the other universes; we didn’t really need them anyway.

Nondeterminism’s Magic Wand

The preceding section is rather silly, but it is the underlying idea behind computational nondeterminism. When we come to a choice we nondeterministically take all of the choices, and then once we have the benefit of hindsight to know which choice was correct we go back and un-choose the other options. It’s a strange idea that no real machine fully mimics, but it turns out to be a powerful idea in theory. We’ll see some of that practical application in a future post.

Nondeterminism lets us magically make the right choice every time, but surprisingly this doesn’t let us magically solve every problem. For example, suppose I have some theory that I want to prove and that I know how to check if a particular piece of text proves that theory. Then I can use nondeterminism to find the proof, if it exists:

Start with a blank piece of text; Repeat until a proof is found { If the text is a proof of the theory { Stop and output the text. } Otherwise { Nondeterministically add a letter to the text. } }

If the theory is provably true, this will always find the proof. If, however, my theory was not provable I’ll never find that out: the program will keep running forever, always looking at longer and longer possible proofs. Even with magically correct guesses, I’ll never know my theory is false.

Nondeterminism is a strange idea. It’s an example of asking far-fetched “‍what if‍” questions and finding answers that turn out to be useful despite their origin. Unlike many other strange-looking but useful theoretic constructs, nondeterminism was introduced with an application Nondeterminism first appeared (as far as I know) in Rabin, M. O. & Scott, D. (1959). “‍Finite automata and their decision problems.‍” IBM Journal of Research and Development 3(2), 636–644. and many more applications have arisen since. We’ll come back to nondeterminism often as we continue to explore theory.