07/06/26 23:49:45
>>276
計算可能な関数に関しては、
Hardy Function を用いて、F[順序数](n) という形に近似して順序数の大小で比較。
Hardy Function を本質的に超える関数が出てくるまでは、
これで大小比較が可能。
（順序数が本質的に大きいかどうかという問題になる）
---例---
Knuthの上矢印 3(↑^n)3 ≒ F[ω](n)
n個のnからなるConwayのチェーン ≒ F[ω^2](n)
↑n (3,3,3) ≒ F[ω^3](n)
Ak(n, 3) = ≒ F[ω](n)
Ak を多変数に拡張、Ak(n個のn) ≒ F[ω^ω](n)
Ak を２重リストに拡張、Ak([n個のn], [n]) ≒ F[ω^ω^ω](n)
Ak を多重リストに拡張、Ak(n重リスト) ≒ F[ε_0](n)
ちなみに、g = f^x(x) とするのは、F[順序数](n) の順序数に1を加えるのと同じ効果。
----
計算不可能なものも含めた場合には、
ある程度小さなものは、
>>230 の形に近似して順序数の大小で比較すれば良いが、
順序数をマシンで生成させ、これを引数とするHALT[順序数] 命令にすると、
M[順序数](n) よりも大きくなるため、順序数での比較は不可になる。