機械が計算する関数

自然数 $x$ を、$x+1$ 個の連続する $1$ のブロック $1^{x+1}$ で表す。$n$ 個の引数 $x_1,\ldots,x_n$ の標準入力とは、テープが

の形で、これ以外の升目がすべて $0$ であり、ヘッドが最左の $1$ を指し、状態が $0$ であるような状況をいう。標準出力 $y$ とは、テープが $1^{y+1}$ 以外すべて $0$ で、ヘッドがその最左の $1$ を指す状況をいう（状態は問わない）。

機械 $M$ が標準入力 $\vec{x}$ から始めて有限ステップで停止し、そのとき標準出力 $y$ になっているならば、$\varphi^{(n)}_M(\vec{x})=y$ と定める。そうでなければ（停止しない、または停止しても標準出力でない）$\varphi^{(n)}_M(\vec{x})\uparrow$ とする。部分関数 $f$ に対して $f=\varphi^{(n)}_M$ となる機械 $M$ があるとき、$f$ はチューリング計算可能であるという。