A nondeterministic Turing machine with a read-only input tape, \(k\) work tapes, and a write-only output tape, over an alphabet of symbols extended by a blank, consists of an initial state \(q_0\) and two transition functions \(\delta _0\) and \(\delta _1\), one for each value of a choice bit. Each \(\delta _b\) maps the current state, the (possibly blank) symbol under the input head, and the \(k\) symbols under the work-tape heads to a one-step action: a movement of the input head, a write-and-move instruction for each work tape, an optional symbol to append to the output, and a successor state or the decision to halt. Neither the alphabet nor the state set is required to be finite.

Let \(M\) be a nondeterministic multi-tape Turing machine with transition functions \(\delta _0, \delta _1\), let \(b \in \{ 0,1\} \) be a choice bit, and let \(c\) be a configuration of \(M\) on a fixed input. The step of \(M\) from \(c\) under \(b\) returns \(c\) unchanged if \(c\) is halted (its state component is empty), whatever the value of \(b\); otherwise it applies to \(c\) the action that \(\delta _b\) prescribes for the current state, the symbol under the input head, and the symbols under the \(k\) work-tape heads.

The starting configuration of a nondeterministic multi-tape Turing machine \(M\) on an input word \(x\): the machine is in its initial state \(q_0\), the input head scans the first symbol of \(x\), all work tapes are blank with their heads at cell \(0\), and the output tape is empty.

Let \(M\) be a nondeterministic multi-tape Turing machine and \(c\) a configuration of \(M\) on a fixed input. For a choice word \(w = b_1 b_2 \cdots b_m \in \{ 0,1\} ^*\), the run of \(M\) from \(c\) under \(w\) is the configuration obtained from \(c\) by performing \(m\) steps of \(M\), the \(i\)-th of them under the choice bit \(b_i\). Recursively, the run under the empty word is \(c\), and the run under \(b w\) is the run under \(w\) from the configuration reached by one step of \(M\) from \(c\) under \(b\).

Let \(M\) be a nondeterministic multi-tape Turing machine, \(x\) an input word, and \(t \in \mathbb {N}\). The machine \(M\) halts on \(x\) within \(t\) steps along every branch if, for every choice word \(w \in \{ 0,1\} ^t\) of length exactly \(t\), the configuration reached by running \(M\) under \(w\) from its initial configuration on \(x\) is halted, that is, has an empty state component.

For an alphabet \(\Sigma \), a finite nondeterministic Turing machine consists of a number \(k \in \mathbb {N}\) of work tapes, a finite state set with decidable equality, and a nondeterministic multi-tape Turing machine with \(k\) work tapes and those states, whose tape cells hold either a symbol of \(\Sigma \) or a blank.

Let \(M\) be a deterministic multi-tape Turing machine with \(k\) work tapes, initial state \(q_0\), and transition function \(\delta \). The associated nondeterministic machine has the same tapes, states, and initial state \(q_0\), and both of its transition functions \(\delta _0\) and \(\delta _1\) are equal to \(\delta \), so that its behaviour does not depend on the choice bit.

Let \(\Sigma \) be an alphabet and \(M\) a finite deterministic Turing machine over \(\Sigma \) with \(k\) work tapes, a finite state set, and transition function \(\delta \). The associated finite nondeterministic Turing machine has the same number \(k\) of work tapes and the same state set, and as underlying machine the nondeterministic machine with the same initial state whose two transition functions both equal \(\delta \).