チューリング機械

チューリング機械（以下、機械）$M$ とは、有限個の規則の集合である。各規則は

の形をしている。ここで $q,q'\in\mathbb{N}$ は状態、$a,b\in\{0,1,2\}$ は記号（$0$ を空白とみなし、$2$ は作業用の目印として使う）、$d\in\{L,R\}$ は移動方向である。各組 $(q,a)$ に対して規則は高々一つしか存在しない。

テープは両側に無限に延びる升目の列で、各升目に $0,1,2$ のどれかが書かれている（有限個を除いて $0$）。ヘッドは升目の一つを指す。状況（configuration）とは、テープの内容、ヘッドの位置、現在の状態の組である。

機械は状態 $0$ から始める。状況が $(q,a)$（$q$ は現在の状態、$a$ はヘッドの下の記号）のとき、規則 $(q,a)\mapsto(q',b,d)$ があれば、1 ステップで次のことを行う。ヘッドの下の記号を $b$ に書き換え、$d$ の方向に升目を一つ移動し、状態を $q'$ にする。該当する規則がなければ停止する。