Here, for example, is a non-deterministic, one-way finite-state machine. This machine "accepts" input strings that have either a string of four consecutive A's or three consecutive B's.
Unlike a normal Turing machine, a non-deterministic machine can do more than one thing in a given state when reading a given input symbol. This means that the machine's computation can simultaneously follow more than one path through its state diagram. To show such a computation, Turing's World produces multiple tapes, one for each path the computation follows. Below is an image of a non-deterministic computation in progress.
Turing's World Table of Contents.
Return to Logic Software from CSLI.