グッドスタインの定理
グッドスタインの定理を応用すると、全域関数であって、かつ全域関数であることがペアノ算術では証明できないような計算可能関数を構成できる。個々の数のグッドスタイン数列はチューリングマシンによって算出できる。したがって、n を「n のグッドスタイン数列が停止するまでに要する項の数」に対応づけるような関数も、何らかのチューリングマシンによって計算できる。この計算機は単に n のグッドスタイン数列を算出し、もし数列が 0 に収束したならば、その数列の長さを返すだけである。全てのグッドスタイン数列は最終的には収束するので、この関数は全域関数である。ところがペアノ算術からは全てのグッドスタイン数列が収束することは証明できないので、ペアノ算術はこのチューリングマシンが計算しているのが全域関数であることを証明できない。