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

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

巨大数探索スレッド10

42 :132人目の素数さん:2014/01/03(金) 07:49:25.19
ラヨ関数の定義に神託式を加えると本当にずっと増大度の大きい関数が得られるのかが気になってきた。

ビジービーバー関数のチューリングマシンに神託を加えるとずっと増大度の大きい関数が得られるのは、
有限の時間では計算できなかった関数が有限の時間で計算できるようになるからである。

もし、ラヨ関数の定義で扱っているのがFOSTで「証明」可能な式ならば、神託式を加えることで
有限の長さでは証明できなかった式が有限の長さで証明できるようになり、
ずっと増大度の大きい関数が得られることになる。

しかし、ラヨ関数の定義で扱っているのはFOSTで「表現」可能な式である。
もしラヨ関数の式をFOSTの式で表現することが可能ならば、神託式を加えても
有限の長さで表現できた式をより短く表現できるようになるだけで、関数の増大度はほとんど変わらない。
というのも、式φ_1とφ_2が同値ならばSat([φ_1],s)とSat([φ_2],s)も同値となる。
神託式を用いてRayo(10^100)を表した式φ_1と同値なFOSTの式φ_2が10^100文字以下で表されるならば、
φ_2が定義する数はRayo(10^100)よりも小さいか、一つの数を定義しないかのどちらかになる。
前者は矛盾しているので、φ_2は一つの数を定義しないことになる。
すると、神託式を用いてRayo(10^100)を表した式φ_1も一つの数を定義しないことになってしまう。

ここから考えられる可能性は、
1. 神託式を形式的に導入しても、神託式が実質的に効力を発揮することはない。
2. ラヨ関数を表す式はFOSTで表現できない。
(つまり、ふぃっしゅ数バージョン7のwikiのページの議論で、
>ラヨ数のマイクロ言語(FOST)の中で、ラヨ関数を計算する式を立てることは可能であると思われる。
と書かれているのは誤りということになる。)
3. ラヨ関数(およびラヨ数)は定義できない。(値が一つに定まらない)
4. 上の議論自体が間違っている。
のいずれかになる。数理論理学に詳しい人の説明がほしいところだ。

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

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

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