- When the automaton is faced with a choice,
it always (magically) chooses correctly.
We sometimes think of of the automaton as
consulting an
*oracle*which advises it as to the correct choice. - When the automaton is faced with a choice, it spawns a new process, so that all possible paths are followed simultaneously.

There are three ways, two feasible and one not yet feasible, to simulate the second alternative:

- Use a recursive backtracking algorithm. Whenever the automaton has to make a choice, cycle through all the alternatives and make a recursive call to determine whether any of the alternatives leads to a solution (final state).
- Maintain a state set or a state vector, keeping
track of
*all*the states that the nfa could be in at any given point in the string. - Use a
*quantum computer*. Quantum computers explore literally all possibilities simultaneously. They are theoretically possible, but are at the cutting edge of physics. It may (or may not) be feasible to build such a device.

Copyright © 1996 by David Matuszek

Last modified Jan 29, 1996