5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

巨大数探索スレッド10

712 :132人目の素数さん:2015/08/05(水) 16:04:26.60 ID:Gr29kBRF
最後に、一見非効率的な関数を超える関数はなさそうに見えるが、
ちゃんとこれには拡張性がある。

非効率的な関数f(n)は、自然言語で扱える関数の中には当然ない。
よって、f(n)を無前提で使える関数としてもつ言語、自然言語+f(n)
は、(オラクル付きのチューリングマシンがより強力となるように)強力な言語になる。

よってハーディ関数的に、H[0](n)=f(n),
H[α](n)=(自然言語+H[β](m)、ただしβ<α、n文字以内で定義できない最小の数)
とできる。しかし、H[β](m)を使うなら、βがどのような順序数なのかの説明文も
n文字以内の文の中に含ませないと、値が決まらなくなってしまう。

これの面白いところは、ハーディ関数と違い、扱える順序数が、収束列のある
帰納的順序数に制限されないことである。しかし、どこまで大きな順序数が入るのか、
例えば到達不能基数に対応した順序数を入れて意味があるのか、というのは分からない。

例えば、最小の非可算順序数Ωを入れてみる。すると、任意の可算順序数αについて、
H[α](n)を使用できるわけだが、αがどんな順序数なのかは説明しないといけない。だが、可算順序数は2^アレフ0個あるので、
可算順序数の中には説明できないものがある。そこで、任意の記述可能な可算順序数よりも大きい最小の可算順序数をγとすると、
任意のγ以上Ω以下の順序数δ1,δ2について、(意外にも)H[δ1](n)=H[δ2](n)となる。

他、順序数版の非効率的な関数を加えた言語を考えることで、さらに拡張できる。

347 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.02 2018/11/22 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)