交替性チューリング機械
M が状態 q ∈ Q {\displaystyle q\in Q} にあり、 g ( q ) = a c c e p t {\displaystyle g(q)=accept} なら、受理状態であることを示している。また g ( q ) = r e j e c t {\displaystyle g(q)=reject} なら、拒絶状態であることを示している。 g ( q ) = ∧ {\displaystyle g(q)=\wedge } なら、1ステップで到達可能な全ての構成が受理状態であれば、受理状態であるし、1ステップで到達可能な状態の中に拒絶状態のものがあれば、拒絶状態である。 g ( q ) = ∨ {\displaystyle g(q)=\vee } なら、1ステップで到達可能な状態の中に受理状態のものがあれば、受理状態であるし、1ステップで到達可能な全ての構成が拒絶状態であれば、拒絶状態である(通常の NTM は全てこの状態)。M が入力文字列 w を受理するとは、M の初期構成(Mの状態が q 0 {\displaystyle q_{0}} で、ヘッドはテープの左端にあり、テープには w がある)が受理状態であることを意味し、初期構成が拒絶状態なら拒絶する。
交替性チューリング機械で解ける最も単純な問題として限量記号付きブール式問題がある。これは充足可能性問題を拡張して、各変数が存在量化子か全称量化子で制限されるようにした問題である。交替性チューリング機械は、存在量化された変数については存在的に分岐して考えられる全ての値を試し、全称量化された変数については全称的に分岐して考えられる全ての値を試す。これを量化される順に左から右に見ていくのである。全ての量化変数の値を決定した後、論理式にそれらの値を適用して、その真理値によって受理か拒絶かを決定する。
このような機械は限量記号付きブール式を、時間 n 2 {\displaystyle n^{2}} と領域 n {\displaystyle n} で決定する。
充足可能性問題は、全ての変数が存在量化された特殊ケースと見ることもでき、存在的様式だけで効率的に解ける。