Let \(N\) be a nondeterministic multi-tape Turing machine over the binary alphabet with finitely many states and two transition functions, one for each choice bit; let \(x\) be a binary string and \(t \in \mathbb {N}\). We say that \(N\) accepts \(x\) within \(t\) steps if there is a choice word \(w \in \{ 0,1\} ^t\) such that running \(N\) from its initial configuration on input \(x\) for \(t\) steps, using the \(i\)-th bit of \(w\) to select the transition function at step \(i\), reaches a halted configuration whose output is exactly the one-bit string \(1\). A branch halted with any other output, including the empty string and \(0\), is not accepting.

Let \(N\) be a finite nondeterministic multi-tape Turing machine over the binary alphabet, let \(L\) be a language of binary strings, and let \(T : \mathbb {N} \to \mathbb {N}\). We say that \(N\) decides \(L\) within time \(T\) if for every binary input \(x\): every choice word of length \(T(|x|)\) drives \(N\) from its initial configuration on \(x\) to a halted configuration, and \(x \in L\) if and only if some choice word of length \(T(|x|)\) drives \(N\) on \(x\) to a halted configuration with output exactly the one-bit string \(1\).

For a time bound \(T : \mathbb {N} \to \mathbb {N}\), the class \(\mathrm{NTIME}(T)\) consists of all languages \(L\) of binary strings for which there exist a constant \(c \in \mathbb {N}\) and a finite nondeterministic multi-tape Turing machine \(N\) over the binary alphabet such that, on every input \(x\), every choice word of length \(c \cdot T(|x|)\) drives \(N\) to a halted configuration, and \(x \in L\) exactly when some choice word of that length drives \(N\) to a halted configuration with output \(1\).