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

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

巨大数探索スレッド10

709 :132人目の素数さん:2015/08/05(水) 14:43:01.72 ID:Gr29kBRF
ラヨ関数、及びBIG FOOTを超える関数について考察してみた。
とはいえ、あまり意味のあるものとは言えないかもしれないが...

自然数の集合の濃度(可算濃度)をアレフ0として、
すべての自然数から自然数への関数からなる集合の濃度は、アレフ0^アレフ0
(任意のnについて、f(n)の値の選び方がアレフ0通りあるから)
ちなみに、アレフ0^アレフ0 = 2^アレフ0 である。

一方で、言語によって定義できる関数はアレフ0個しかない。以下でそれを示す。
我々が普段使う言語(以下自然言語)は、有限種類の文字(記号)からなる。
文字の種類をnとし、すべての文字に何らか番号をふってL1,L2,L3,...,Lnとする。
自然言語で表現できる文を、
L1, L2, ..., Ln, L1L1, L1L2, ..., L1Ln, L2L1, ..., LnLn, L1L1L1, ...
と列挙することができる。
よって明らかに自然言語で表現できる文と、自然数とで一対一対応がとれるため、
自然言語で表現できる文からなる集合と、自然数からなる集合の濃度は一致する。

ゆえに、自然数から自然数への関数は2^アレフ0個もあるのに、
有限文字の自然言語で定義できる関数はアレフ0個しかないため、
有限文字では記述不能な関数が存在する。(以下記述不能関数と呼ぶ)

そして、ほとんどの実数は自然数でないのと同様に、ほとんどの関数は記述不能関数であると言える。

ベリーのパラドックスのような、「「17文字以内で定義できない最小の数」が17文字で定義されている」
といった問題は、f(n) = (n文字以内で定義できない最小の数) という関数が
記述可能だと仮定するために生じる問題であって、f(n)が記述不能関数ならば問題ない。

そして、無限文字(厳密にはアレフ0文字)使っていいなら、任意の自然数から自然数への関数を、例えば
f(1)=2, f(2)=10, f(3)=90, ...といった形で無限に書くことで表現できるため、無限文字なら記述不能関数を記述できる。

よって、ラヨ関数やBIG FOOTが矛盾を含んでいないなら、これらは当然自然言語で表現された関数なのだから、
記述不能関数の1つであるf(n) = (自然言語n文字で定義できない最小の数)より弱い、ということになる。

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

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

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