整った機械

$n$ 変数の部分関数 $f$ について、機械 $M$ が整っているとは、すべての標準入力 $\vec{x}$ から始めた動作が次を満たすことをいう。ヘッドの最初の位置（最左の $1$）を $p$ とする。

• (a) $M$ が停止するのは、升目 $p$ 以右の内容が標準出力（一つのブロック $1^{y+1}$ 以外すべて $0$）になっていて、ヘッドがその最左の $1$ を指しているときに限り、そのとき $y=f(\vec{x})$ である。特に $f(\vec{x})\uparrow$ ならば $M$ は停止しない。（以下、標準出力といえばこの意味、すなわち升目 $p-1$ 以左の内容は問わない。）
• (b) $M$ は升目 $p-2$ 以左を訪れない。升目 $p-1$ には移ってよいが、そこでは書き込まない。