巨大数探索スレッド9
■ このスレッドは過去ログ倉庫に格納されています
0893紫陽花
2013/08/10(土) NY:AN:NY.ANチューリングマシンは有限順序数(自然数)しか扱えないので、
ck=lim{BB(1),BB(2),BB(3),...}=ωとなってしまいます。
チューリングマシンにオラクルを与えても、ωを超える順序数は表せません。
すべての帰納的順序数関数を計算できる計算模型があるならいいのですが、
(確かに、Kleene's O とかNathanael Leedom Ackerman氏の
ordinal turing machineとか無限時間チューリングマシンとか
それらしいのはたくさんあります)大きな順序数を生み出してかつ
その収束列まで定義してくれる計算模型というのは、
あったとしても少なくとも普通のチューリングマシンではありません。
(そして私は、無限時間チューリングマシンについては大きな順序数
は作れても、それに収束列を与えることはできないと考えています。)
仮に、先述の条件を満たす計算模型を定義できても、例えばBB(x)を
オラクルとして与えるとckから帰納的に導ける順序数をすべて表せるか
どうか、というのは疑問に思います。
また、f(x)=x+1の合成回数をアルゴリズムがある方法で決めた関数は
H[1×α](x)(αは帰納的順序数)の形で表せ、その形では到達できない
関数の1つとしてBB(x)を選びこれをH[1×ck](x)と名づけ、
BB(x)の合成回数をアルゴリズムがある方法で決めた関数(つまり
BB(x)の帰納的拡張)をH[ck×α](x)と名づけるのは妥当だと
思います。そして、この形では到達できない関数の1つとして
B[2](x)を選び、これをH[ck×ck](x)と名づけるのも妥当
だと思います。
■ このスレッドは過去ログ倉庫に格納されています