Nondeterministic Turing Machines

In theoretical computer science, there is a theorem which states that all nondeterministic Turing machines (NTM) have an equivalent deterministic Turing machine (DTM). NTMs differ from DTMs in that the former allow for the possibility of more than one next state from a given configuration.

If there is more than one next move, we do not specify which next move the machine makes, only that it chooses one such move.

source: Computability and Complexity Theory, Steven Homer & Alan Selman, p.31

The proof for the theorem that NTMs have equivalent DTMs is through construction: the DTM builds NTM’s computation tree and then performs a breadth-first search on this tree. I was never convinced by this proof. If you take time into consideration, and the fact that NTM’s computation tree approaches infinity in size due to the size of the option set from which it ‘chooses’ at each step, you get a search that takes the DTM forever (or almost forever) to complete (which, to borrow Douglas Bridges’ expression, “does not extend to an assurance that you will find the desired term before the end of the universe”). I remain unconvinced that NTMs are equivalent to DTMs.

[Photomedia Forum post by T.Neugebauer from Jun 20, 2006]