Nondeterministic Turing machine

A Turing machine whose transition rules can allow multiple next moves. It accepts an input when at least one possible computation path reaches an accepting state.

Configuration (computability): A snapshot of a Turing machine’s state, tape contents, and head position during a computation. Each branch begins from a configuration and generates successor configurations.
NP: The class of decision problems whose yes-instances have certificates verifiable in polynomial time. A nondeterministic polynomial-time machine accepts exactly the languages in NP.
Turing machine: An abstract machine that computes by reading and writing symbols on a tape according to finite-state rules. Nondeterministic Turing machines extend this general model with multiple permitted moves.
Deterministic simulation of a nondeterministic Turing machine: A deterministic computation that explores or encodes the possible paths of a nondeterministic machine. It shows how branching can be simulated, often with substantial time overhead.
Computation tree: A tree whose nodes are configurations and whose edges represent possible computation steps. It displays all branches that the transition rules permit on one input.
P versus NP problem: The open question of whether every problem with efficiently verifiable solutions can also be solved efficiently. It asks whether nondeterministic polynomial-time computation can be simulated efficiently by deterministic computation.
Transition function: A rule mapping a machine’s current state and scanned symbol to permitted next states and actions. Allowing multiple outcomes for one state-symbol pair creates branching.
Alternating Turing machine: A Turing machine with existential and universal states, combining choices that represent different logical quantifiers. It extends existential acceptance with universal requirements across branches.
Accepting state: A designated machine state that marks successful completion of a computation. Acceptance requires at least one branch to reach such a state.
Nondeterministic time: A complexity measure bounding the number of steps along every computation path of a nondeterministic machine. It measures resources used by this machine model.

Linked from 5 pages