Nondeterministic Turing machine

In theoretical computer science, a nondeterministic Turing machine (NTM) is a special kind of computer that scientists imagine when they study how computers work. Unlike regular computers, an NTM can choose more than one action at once when it has a problem. This means its next step isn't always obvious — it has several choices.

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 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 what computers can and cannot do.

Background

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

In a deterministic Turing machine, there is only one action the machine can take in any 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. It 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 helps it explore many paths at once, like a thought experiment to see what computers can do.

The machine has six parts: states it can be in, symbols it can read and write, a starting state, a blank symbol for empty spaces, final states that mean "yes", and rules for moving and changing symbols. Unlike regular machines, these rules can pick several next steps. If any path ends in a final state, the machine says "yes" to that input.

Computational equivalence with DTMs

Any problem a deterministic Turing machine (DTM) can solve, a nondeterministic Turing machine (NTM) can solve too, and the other way around. But people think the time it takes might be different.

NTMs include DTMs as special cases. This means every calculation a DTM can do, an NTM can do as well.

It might seem like NTMs are stronger because they can look at many paths at once. But it is possible to copy what an NTM does using a DTM in different ways. One way is for the DTM to remember many steps of the NTM at once. Another way uses extra tapes to follow the NTM's paths.

The big question in computer science is called the P versus NP problem. It 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.

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