JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Nondeterministic Turing Machines

Give a Turing machine the NFA's old superpower — the ability to fork and try every choice at once — and you get a machine that is easier to design but no stronger. This guide shows exactly how a deterministic machine simulates a nondeterministic one by searching its tree of guesses, why that simulation can cost an exponential slowdown, and how the same idea quietly becomes the definition of the class NP.

An old superpower on a new machine

Way back on the finite-automaton rung you met a machine that could clone itself. A nondeterministic finite automaton reading an 'a' did not have to pick one next state — it could split into copies, one per allowed choice, and explore every branch in parallel, accepting if any single copy ended up happy. A nondeterministic Turing machine (NTM) is exactly that same superpower bolted onto the endless read-and-rewrite notebook of an ordinary Turing machine. Its transition rule no longer hands back one move; it hands back a set of moves, and the machine is imagined to try them all at once.

Concretely, where a deterministic machine has a rule like 'delta(q, a) = (p, b, R)' — in state q reading 'a', write 'b', move right, go to state p — a nondeterministic machine has rules of the form 'delta(q, a) = a SET of such triples'. Reading the same 'a' in state q, it might write-b-and-go-right-to-p, OR write-c-and-go-left-to-r, OR do a third thing. We say the NTM accepts an input when SOME sequence of choices leads it to the accept state. One lucky branch is enough; the unlucky branches do not matter. This is the 'guess, then check' shape you saw with the NFA, now with a full read/write tape to do the checking on.

The picture: a branching tree of configurations

The cleanest way to picture an NTM's run is as a tree, not a line. A deterministic machine on a fixed input traces a single path: configuration after configuration, each forced by the rules, marching forward until it halts (or never does). A complete snapshot of the machine at one instant — the state, the tape contents, and where the head sits — is one configuration. For the NTM, each configuration can have several legal successors, so instead of a path we get a tree that branches every time a choice is offered.

The root of the tree is the start configuration. Each node's children are all the configurations reachable in one step. A branch where some copy reaches the accept state is an accepting branch. The NTM accepts the whole input exactly when the tree contains at least ONE accepting branch — anywhere, however deep. So the meaning of 'this NTM accepts x' is really a statement about the existence of a path through a tree, and the job of running it for real is the job of searching that tree.

                 [ start config ]                depth 0
                  /      |       \
            cfg A      cfg B      cfg C            depth 1
            /  \        |         /  \
        ...    cfg     cfg      ...   ACCEPT  <-- one lucky branch
                |       |              (the whole NTM accepts)
              REJECT   loop...

  accept x  <=>  SOME leaf in the tree is an accept state
  branching factor b, depth up to t  =>  up to b^t configurations
The computation of an NTM is a tree. Acceptance means at least one branch reaches accept; a deterministic simulator must search this whole tree.

Determinism catches up — by searching the tree

Here is the headline result, and it should feel familiar: a nondeterministic Turing machine is no more powerful than a deterministic one. Anything an NTM can do, an ordinary deterministic Turing machine can do too. This is the deep echo of NFA–DFA equivalence one rung up: there the subset construction turned 'try all branches' into 'track the set of states you could be in'. Here the trick is even more direct — we just have the deterministic machine systematically explore the NTM's tree of configurations and watch for an accepting branch.

The one subtlety is HOW you explore the tree. The naive idea — walk all the way down the first branch, then the next — is fatal, because that first branch might loop forever, and you would be stuck on a non-accepting path while an accepting one waits two branches over, never reached. So the simulator must explore breadth-first: examine every branch of depth 1, then every branch of depth 2, then depth 3, and so on. This way, if any accepting branch exists at some finite depth d, the search is guaranteed to reach it after finishing all the depth-d work. A multitape layout makes the bookkeeping clean: this is exactly the kind of job the multitape machine from the previous guide was built to keep tidy.

  1. Address every node of the tree by the sequence of choices that reaches it, e.g. the string '2-1-3' means 'at the first branch take choice 2, then choice 1, then choice 3'. Keep this address on a dedicated 'choices' tape.
  2. To test one address, copy the original input onto a work tape, then re-run the NTM deterministically, at each branch obeying the next digit of the choices tape. If a digit asks for a choice that does not exist, abandon this address as invalid.
  3. If this simulated branch reaches the accept state, halt and accept the whole input. If it rejects or runs out of choices, move on.
  4. Generate the addresses in shortlex order — all length-1 strings, then all length-2, and so on — which is exactly breadth-first search of the tree, so a finite-depth accepting branch is always found.

Equivalent — but at what cost?

So an NTM computes nothing a deterministic machine cannot. This is another pillar of the robustness of the Turing-machine model: just as adding many tapes did not change WHAT can be computed (only the speed), adding nondeterminism does not change it either. The class of languages an NTM can recognize is exactly the Turing-recognizable languages, and the class it can decide is exactly the decidable ones. Nondeterminism, like extra tapes, is a convenience — a way to design and describe machines more easily — not a way to compute genuinely new things.

But notice how different this feels from the multitape result. Converting a multitape machine to a single tape cost only a polynomial slowdown — slower, yes, but only mildly. The tree search above is far more expensive. If the NTM's tree has branching factor b and an accepting branch at depth t, there can be on the order of 'b^t' configurations to examine, so the deterministic simulator may take exponential time in t. Best known general bound: simulating t steps of an NTM costs the deterministic machine roughly '2^(O(t))' steps. We can match the POWER cheaply; matching the SPEED, as far as anyone knows, may cost an exponential blowup.

Why this fiction matters: guess, then verify

Even though no NTM exists in hardware, the model is one of the most useful tools in the whole theory, for the same reason the NFA was: it is far easier to DESIGN a 'guess-and-verify' machine than a from-scratch deterministic one. The recipe is guess, then verify: at the branching step, let the machine nondeterministically write down a candidate answer — a possible factorization, a possible tour through a graph, a possible coloring — and then run an ordinary deterministic check that this candidate really works, accepting only if it does. Because the machine accepts when SOME branch succeeds, this is logically identical to saying 'there exists a candidate that passes the check'.

This guess-and-verify shape is not just a design convenience — it is, almost word for word, the definition of one of the most important classes in computer science. The class NP is the set of problems an NTM can decide in polynomial time; equivalently, it is the set of problems whose 'yes' answers come with a short certificate that a deterministic machine can check quickly. The nondeterministic guess IS the certificate; the deterministic check IS the verifier. NP is the formal home of the jigsaw-puzzle problems: hard to finish, but easy to check once a solution is handed to you.

And now the loop closes. The 'merely an exponential slowdown' from the previous section is precisely the question of whether every NP problem can be solved deterministically in polynomial time — that is, whether P equals NP. Be careful with the name: NP stands for 'nondeterministic polynomial time', NOT 'non-polynomial'; in fact every problem solvable in deterministic polynomial time is trivially in NP, so P is a subset of NP. Whether the two classes are actually equal is open, and unproven, and worth a great deal of fame to whoever settles it. Two rungs from now you will meet it head-on; for today it is enough to see that the innocent-looking nondeterministic Turing machine is the seed from which that entire question grows.