非決定性チューリングマシン
形式的には、非決定性チューリング機械は6タプル M = ( Q , Σ , ι , ⊔ , A , δ ) {\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )} で表され、以下のような意味を持つ。
Q {\displaystyle Q} は状態群の有限な集合である。
Σ {\displaystyle \Sigma } は記号群(テープ上のアルファベット)の有限な集合である。
ι ∈ Q {\displaystyle \iota \in Q} は初期状態である。
⊔ {\displaystyle \sqcup } は空記号である ( ⊔ ∈ Σ {\displaystyle \sqcup \in \Sigma } )。
A ⊆ Q {\displaystyle A\subseteq Q} は受理状態の集合である。
δ : Q ∖ A × Σ → ( Q × Σ × { L , R } ) {\displaystyle \delta :Q\backslash A\times \Sigma \rightarrow \left(Q\times \Sigma \times \{L,R\}\right)} は遷移関数であり、状態と記号に関する多価関数である。ここで、L はテープヘッドの左シフト、R は右シフトを表す。普通のチューリング機械では遷移関数は多価ではない。