(>>29の続き)
とすると

初期状態{Tape(0), State(0), Position(0)}が与えられていると仮定する。
補題1
Tape(0)[-Infinity .. Infinity]に含まれる値の個数は高々加算無限個なので、
ある関数fが存在し、Tape(0)に存在する全ての値rは、ある整数iが存在し、f(i) = rを満たす。

補題2
整数は自然数に一対一対応可能なため、ある関数gが存在し、Tape(0)に存在する全ての値rは、
ある自然数nが存在し、g(n) = rを満たす。

定理3
g(-n-1) = Delta(State(n), Tape(n)[Position(n)])を満たすように関数gを選ぶ。この時
任意の非負整数nに対し、Tape(0..n)に含まれる値の個数は可算無限個である。

証明3
帰納法による。
n = 0の時、Tape(0..n)に含まれる値の個数は可算無限個である。
n = kの時にTape(0..k)に含まれる値の個数が可算無限個であると仮定する。
n = k + 1の時、Tape(k)に含まれず、かつTape(k + 1)に含まれるような値が存在するとすれば、
その値はDelta(State(k), Tape(k)[Potision(k)])と等しい。
その値をg(-k-1)と置くと、Tape(0..k+1)に含まれる値は全て
ある関数gを用いて整数と一対一対応可能である為
Tape(0..n)に含まれる値の個数は加算無限個である。