Nondeterministic Turing machine

In theoretical computer science, a nondeterministic Turing machine (NTM) is a special kind of computer that scientists use only in their minds to study how computers work. Unlike regular computers, an NTM can choose more than one thing to do at once when it faces a problem. This means its next step isn't always clear — it has several options to pick from.

People use NTMs in thought experiments to understand what computers can and cannot do. They help scientists explore big questions, like how hard it is for regular computers to solve certain kinds of problems. One of the biggest puzzles in this area is the P versus NP problem, which asks whether problems that are easy for an NTM to solve can also be solved easily by regular computers. These ideas help us learn more about the power and limits of computing.

Background

A Turing machine is like a simple imaginary computer. It reads and writes symbols one at a time on a very long tape, following strict rules. It decides what to do next based on its current situation and the symbol it sees.

In a deterministic Turing machine, there is only one action the machine can take in any given situation. For example, if the machine sees an X in a certain state, it knows exactly what to write, which way to move, and what state to change to next.

Description

A nondeterministic Turing machine (NTM) is a special kind of computer that can choose between different actions at any moment. Unlike regular computers that follow one path at a time, an NTM can pick from several options. For example, if it sees a letter “X” and is in a certain step, it might change the letter to “Y” and move right or it might keep the “X” and move left.

Because of these choices, an NTM can explore many paths at once, like branches of a tree. If any of these paths leads to a successful result, the NTM is considered to have accepted the input. This idea helps scientists think about the limits of what computers can do.

Main article: Computation tree

Formal definition

A nondeterministic Turing machine is a special kind of machine used in computer science. It is different from regular machines because it can choose from more than one action at a time. This means it can explore many paths at once, like a thought experiment to see what computers can and cannot do.

The machine is defined by six parts: a set of states it can be in, symbols it can read and write, a starting state, a blank symbol for empty spaces, a set of final states that mean "yes", and a set of rules for moving and changing symbols. Unlike regular machines, these rules do not pick just one next step — they can pick several. If any of these paths ends in a final state, the machine says "yes" to that input.

Computational equivalence with DTMs

Any problem that a deterministic Turing machine (DTM) can solve can also be solved by a nondeterministic Turing machine (NTM), and vice versa. However, people think that the time it takes might not be the same for both.

NTMs include DTMs as special cases, meaning every calculation a DTM can do, an NTM can do too.

It might look like NTMs are stronger because they can explore many paths at once, but it is possible to mimic NTMs using DTMs in different ways. One way is to have the DTM keep track of many steps of the NTM at once. Another way uses extra tapes to follow the NTM's paths.

The big question in computer science, called the P versus NP problem, asks whether problems solved quickly by an NTM can also be solved quickly by a DTM.

Main article: P versus NP problem

Bounded nondeterminism

A nondeterministic Turing machine (NTM) has a special property called bounded nondeterminism. This means that if an NTM always stops working on a certain input, it will stop after a certain number of steps. Because of this, it can only have a limited number of different setups during its work.

Comparison with quantum computers

Quantum computers use special units called quantum bits, which can exist in many states at once. Some people think this means quantum computers work like nondeterministic Turing machines, but experts believe they are different.

While both can explore many paths at once, quantum computers end up with just one random result. Nondeterministic Turing machines, however, can choose the correct answer from all possibilities. This means some problems might be easier for one type of computer than the other.