Nondeterministic Turing Machine
A Turing machine with nondeterministic instruction set. Meaning:
For a configuration C, it has more than one instruction resulting in different configurations. For example one moves the head right and writes 0, one moves the head left and changes state.
When in such configuration with k branches:
- The Turing machine magically spawns k copies of itself, each taking one branch of computation.
- If ANY of the spawned TMs reach the answer in time T, we say the whole TM reached the answer in time T
They are of course not physically possible!