Can a machine explore every possible solution at once? Meet the nondeterministic Turing machine.
In short: Standard computers follow a single, rigid path of logic. A nondeterministic Turing machine, however, can branch into multiple possibilities simultaneously. If any one of these paths leads to an answer, the machine succeeds. This theoretical model is the key to understanding the most famous unsolved problem in computer science.
In 1936, Alan Turing introduced the Turing machine as a model for computation, where a machine reads symbols on a tape and follows a strict, predefined set of rules. A deterministic Turing machine (DTM) is limited to one specific action for any given state and symbol. In contrast, a nondeterministic Turing machine (NTM) allows for multiple potential actions in the same situation. Rather than following a single linear path, an NTM generates a computation tree of possibilities.
The power of an NTM lies in its acceptance criteria: if at least one branch in its computation tree reaches an 'accept' state, the machine accepts the input. While it might seem that NTMs are inherently more powerful than DTMs, they are computationally equivalent; any problem solvable by one can be solved by the other. The crucial difference is time complexity. Simulating an NTM on a DTM typically requires a breadth-first search of the computation tree, which often results in exponential time growth relative to the NTM's shortest path.
This relationship sits at the heart of the P versus NP problem, the most significant open question in theoretical computer science. It asks whether problems solvable by an NTM in polynomial time can also be solved by a DTM in polynomial time. Despite common misconceptions, quantum computers are not NTMs. While quantum machines can exist in superpositions, measurement collapses them into a single, random branch, whereas an NTM is effectively allowed to 'choose' the correct solution among exponentially many branches. Experts believe the capabilities of quantum computers and NTMs are likely incomparable.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Nondeterministic Turing machine
To cite this card, link to https://intellectplus.co.uk/app/science-nondeterministic-turing-machine.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?