■■C++で大きな数を作るスレ■■
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2009/03/24(火) 20:27:50以下のプロトタイプの関数の戻り値で出来るだけ大きな数を返すものを作りましょう。
int main();
●ルール
最大でも１スレに収まる範囲とし、
１スレで完結したプログラムとしてください。
文字数も書いてください
●言語仕様
言語は C++ 2003 準拠とします
int と float は十分な精度があるとします
メモリは十分にあるとします
実行時間は問わないこととします
機種依存、コンパイラ依存の値が返るプログラムは不可
プリプロセッサ、ライブラリの使用は不可
●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
0411デフォルトの名無しさん
2010/07/05(月) 19:52:49>>1
0412デフォルトの名無しさん
2010/07/05(月) 21:05:380413デフォルトの名無しさん
2010/07/05(月) 23:34:02>>398はもしもBB(BB(10000))で不十分だったらという前提で話をしているから。
0414デフォルトの名無しさん
2010/07/05(月) 23:39:50> 初期のマイコンのアセンブラレベルのインタープリタなら比較的簡単に作れる。
> これを用いれば、より記述効率の良いインタープリタが作れる。
> それを用いてC++のインタープリタが作れる。
> それほど大きな差はないはずだという根拠はこれだ。
> 1E100ステートあれば十分すぎる。
作り出すことと、計算複雑性の関係が示されていない。これじゃダメ。
ところで、ビジービーバー関数なら、BB(BB(10000))は計算可能なの？
あるいは、計算可能かつBB(BB(10000))以上である数値を返す関数は存在するの？
0415デフォルトの名無しさん
2010/07/05(月) 23:48:18計算可能。むしろ有限のnならBB(n)は計算可能。
つまり>>402の方法が可能。
0416デフォルトの名無しさん
2010/07/06(火) 18:52:20厳密な証明でなくてもいいと言ってるわりには
結構細かいところをつっこんでくるんだな。
作れるってのは現実的なステート数で作れるってことだよ。
チューリングマシン語を使って簡単なインタープリタを作るのは、
考えてみると結構面白いので一度考えてみることを勧める。
個人的にも十分作れるサイズで出来る。
ヒントを言うと、
普通のチューリングマシン数ステートで
マルチトラックチューリングマシン1ステートを表現できる。
マルチトラックチューリングマシンで、
（上限無しの）整数レジスタ数本と無限長ビットフィールド数本を表現出来る。
初期マイコンのアセンブラの命令を使ってC++のインタープリタを作った場合のサイズは、
現在いろんなコンパイラやデバッグツール、変換ツール、シミュレータが存在してることと、
人類が今まで作ったデジタルデータ量の合計を考えてみれば大まかな予想が出来るはず。
1E100ステートあれば十分すぎる。
0417デフォルトの名無しさん
2010/07/06(火) 19:00:50すべての自然数nに対し、アルゴリズムAが存在し、Aは入力値nに対しBB(n)を出力する
アルゴリズムAが存在し、すべての自然数nに対し、Aは入力値nに対しBB(n)を出力する
これの違いを考えてみることを勧める。
記号で書くと、
∀n, ∃A s.t. Aは入力値nに対しBB(n)を出力する
∃A, ∀n s.t. Aは入力値nに対しBB(n)を出力する
これの違い。
0418デフォルトの名無しさん
2010/07/06(火) 22:24:12> ところで、ビジービーバー関数なら、BB(BB(10000))は計算可能なの？
すべての自然数nに対して BB(n) が計算できるアルゴリズムは存在しない。
（BBは計算不可能であるという）
一方、BB(BB(10000)) という1つの整数に対して計算可能かどうか？
という議論がされることはほとんどない。
BB(BB(10000)) を出力するアルゴリズムの存在は明らかであるから。
n を出力するアルゴリズムを A(n) とした時、
A(1), A(2), A(3), ..... の中に BB(BB(10000)) を出力するものが存在することは明らかなので。
計算理論で計算可能とは有限の情報を用いて有限ステップで終了するアルゴリズムが存在すること。
現実世界で計算が可能であるかどうか、結果が得られるかどうかの評価とは異なり、
メモリ使用量、処理量、実行時間は問わない。
> あるいは、計算可能かつBB(BB(10000))以上である数値を返す関数は存在するの？
f(n) = n だっていずれは BB(BB(10000)) を超えるし、
f(n) = BB(BB(10000))+1 という定数関数ならいつでも超えてる。
0419デフォルトの名無しさん
2010/07/07(水) 01:30:18いや、そこは重要なところだ。
素因数分解が多項式時間でできる量子コンピュータだってチューリングマシンと等価なのだから、
コンピュータで多項式時間でできる処理がチューリングマシンでも多項式時間でできることは別途証明が必要。
0420デフォルトの名無しさん
2010/07/07(水) 01:34:22文字数が0のとき、 10000ステップあれば十分
文字数が1のとき、BB(10000)ステップあれば十分
文字数が2のとき、BB(BB(10000))ステップあれば十分
文字数がnのとき、BB(BB(BB(....BB(10000)....)))ステップあれば十分
0421デフォルトの名無しさん
2010/07/07(水) 18:53:39勘違いしてるかもしれないので書いておくけど、
チューリングマシンのステート数ってのは
計算量や計算時間じゃなくて、
プログラムサイズのことだよ。
プログラムサイズ 1E100語 で
C++プログラムのステップ数を数えるプログラムが出来るって話。
>>420
もっと簡単に、
文字数がnのとき、BB(16*n + 1E100) ステップあれば十分。
0422デフォルトの名無しさん
2010/07/08(木) 01:06:43でもBB(16*n + 1E100) は計算できなさそう。
0423デフォルトの名無しさん
2010/07/08(木) 07:23:17そう。
すべての自然数nに対して BB(16*n + 1E100) を計算出来る単一のアルゴリズムは存在しない。
0424デフォルトの名無しさん
2010/07/08(木) 22:33:46もともと
> 文字数がnのとき、BB(BB(BB(....BB(10000)....)))ステップ
の時点で怪しかったが……
0425デフォルトの名無しさん
2010/07/09(金) 19:21:12C++関数：>>1 の言語仕様を満たす C++の関数
【1】n文字以内のC++プログラムが返すことができる最大値が存在する（この値を Cmax(n) とする）
【2】n文字以内の停止するC++プログラムの最大ステップ数が存在する（この値を Cstep(n) とする）
n文字以内のプログラムは有限個であるため、明らか
ただし、n文字以内のプログラムが存在しない場合は便宜的にCmax(n) = Cstep(n) = 0 としておく
【1】【2】にそれほど大きな差がないことも簡単にわかる
【3】すべてのC++プログラムの停止判定を行えるC++関数は存在しない
【4】すべてのnに対して Cmax(n) を返すC++関数は存在しない
【5】すべてのnに対して Cstep(n) を返すC++関数は存在しない
【4】がα文字で出来たとすると、Cmax(α*2+30) を返すプログラムがα*2+30文字未満で作れる ===> 矛盾
【3】【5】が存在したら【4】も作れる ===> 矛盾
【6】N文字以下のすべてのC++プログラムの停止判定を行えるC++関数は存在する
【7】N以下のすべてのnに対して Cmax(n) を返すC++関数は存在する
【8】N以下のすべてのnに対して Cstep(n) を返すC++関数は存在する
nステップ以下で停止するC++関数を停止すると判断するC++関数を A(n)とした時、
A(1), A(2), A(3), ... の中に【6】が存在することは明らか
【6】から【7】【8】が作れる
0426デフォルトの名無しさん
2010/07/09(金) 19:25:17Cstep(1000) 以上のステップ数を実際に進めてみて停止判定する
【10】【9】のCstep(1000)をどうやってC++関数にするの？
あらかじめ計算して10進数で実装する
【11】【10】を計算することも記述することも事実上出来ないが
【9】を書き下すことは現実的には不可能なの？
Cmax(1000)を1000文字で記述できることはわかっている。
がんばれば人間でもCstep(1000)を超える数を作るプログラムを記述できるかもしれない
現実を考えると、たとえ記述できたとしても実行時間やメモリサイズの制限で完了できない
【12】【11】で作ったものが【10】を超えているという証明は出来るの？
それは非常に難しい。現実的には無理だと思う。
【13】じゃあ結局【6】〜【8】は嘘なの？
確かに存在はするが、それを実際に書き下せることとは別
【14】Cmax(n) てどんな関数？
C++で作れるどんな関数よりも速く増加する関数である
事実上機械的に値を求めることは不可能
各値は >>102 >>227-230 が返す値以上であることはわかっているが
正しい値を知ることは非常に難しい
おそらく Cmax(21) = 9, Cmax(22) = 99, Cmax(23) = 9e9 あたりは正しいと思われる
0427デフォルトの名無しさん
2010/07/09(金) 21:00:50int a=9;int main(){return--a?9<<main():9;} // 42文字
こんな書き方も。
int a;int main(){return--a+9?9<<main():9;} // 42文字
int a;int main(){return++a-9?9<<main():9;} // 42文字
これ以上は無理か？
0428デフォルトの名無しさん
2010/07/09(金) 22:56:05そしたら、N+1文字以下のすべてのC++プログラムの停止判定を行えるC++関数も存在して、
帰納的に【3】が存在することになる気がするんだけど、どこで間違ってるんだろ。
0429デフォルトの名無しさん
2010/07/09(金) 23:18:41N文字以下のすべてのC++プログラムの停止判定を行えるC++関数のうちの1個をA(N)とする。
A(1), A(2), A(3), .... は存在する。...【6】
ところが、
どんな文字数のC++プログラムでも停止判定を行えるようなC++関数 A(∞) は存在しない。【3】
>>417 参照
0430デフォルトの名無しさん
2010/07/10(土) 00:47:23うん。けど、A(N+1)も存在するよね。A(N+2)も存在するよね。
0431名無しさん＠そうだ選挙に行こう
2010/07/10(土) 08:00:35より身近な例で
どんな自然数Nに対しても、それより大きな自然数Mが存在する
ところが、すべての自然数Nよりも大きな自然数Mは存在しない
∀N, ∃M s.t. M>N ...○
∃M, ∀N s.t. M>N ...×
0432名無しさん＠そうだ選挙に行こう
2010/07/10(土) 09:44:32それはしってる。
A(N+1)が存在するかどうか。
0433名無しさん＠そうだ選挙に行こう
2010/07/10(土) 09:55:10なにがわからないのかさっぱりわからないのだが
A(1), A(2), A(3), .... は存在すると書いたがこれが理解できない？
別の書き方で書くと『任意の自然数Nに対して A(N) が存在する』
Nが自然数であればN+1も自然数なので
『任意の自然数Nに対して A(N+1) が存在する』も当然成り立つ
0434名無しさん＠そうだ選挙に行こう
2010/07/10(土) 10:28:21> 任意の自然数Nに対して A(N) が存在する
それはますますわからん。
プログラムの文字数を数える動作が計算可能なら、
その文字数をNとしてA(N)が存在することになるのでは？
そしたら、任意のプログラムの停止判定を行えるA(∞)は存在しなくても
任意のプログラムに対して、そのプログラムの停止判定を行えるA(N)は存在するんじゃないの？
0435名無しさん＠そうだ選挙に行こう
2010/07/10(土) 10:52:45最後の行はYES.
この最後の行と【3】の違いは >>432で 「しってる」と書いてある。
じゃあわからないのは何？
0436名無しさん＠そうだ選挙に行こう
2010/07/10(土) 12:53:21帰納法が無限まで使えないのはどういう場合か。
0437名無しさん＠そうだ選挙に行こう
2010/07/10(土) 13:25:46A(f(code))
でどんなコードでも停止判定できるんじゃないの？
0438437
2010/07/10(土) 13:31:01ls = [A(0), A(1), A(2), ...]の無限リストとして、ls[f(code)]はちょうどA(f(code))になってるわけだ。
0439名無しさん＠そうだ選挙に行こう
2010/07/10(土) 18:29:21じゃあ帰納法の形できちっと証明してみてください。
間違いを指摘してあげるから。
>>437 >>438
A(0), A(1), A(2), ... の無限個のプログラムを持てば出来るって主張？
有限長のプログラムで書けないとアルゴリズムが存在するとは言えないぞ。
>>425 も【4】がα文字で出来たと仮定して矛盾を導いている。
0440名無しさん＠そうだ選挙に行こう
2010/07/10(土) 20:58:14A(0)は存在する。
A(N)が存在するとき、A(N+1)は存在する。
故に任意のNについてA(N)は存在する。
A(N)が存在するとき、N文字のプログラムの停止判定が可能
故に、任意のNについて、N文字のプログラムの停止判定が可能
0441名無しさん＠そうだ選挙に行こう
2010/07/11(日) 07:40:26それは >>425 の【3】の反証にはなってない。
>>417 >>429 >>431 参照。
【3】の反証をしたい訳では無くてただ単に漠然と停止判定が出来るってことなら、
>>429 の A(0), A(1), A(2) ... をくっつけた無限長のC++関数や、
Cstep の値をすべての自然数分保持した無限の情報（オラクル）付きC++関数でも可。
0442名無しさん＠そうだ選挙に行こう
2010/07/11(日) 10:50:19もともと、停止判定にしか興味ないよ。
本当に疑問だったところは、BB(BB(10000))が計算可能ってところで、
それがA(A(10000))の計算に帰着するとしたら、
A(A(10000))の計算はできてもA(A(A(10000)))ができないアルゴリズムを拡張して、
それも計算できるようにするアルゴリズムを得ることはできるか、
できたとしたら、もっと拡張する方法はないか、ということだから。
0443名無しさん＠そうだ選挙に行こう
2010/07/11(日) 20:33:21停止判定を行いたいプログラムよりも停止判定の処理を実行するプログラムの方が能力が上でないとダメ。
たとえ万能の神様でも、自分自身の考えが正しいと判定することは出来ない。
>>442
もともとって、停止判定の話をずーっとしてるんだけど。
A(A(10000)) の記述の意味がわからない。
>>425, >>429 いずれのAの定義でもこんな記述は出来ないと思う。
別の定義の A なら定義を書いて。
-----------
お願いだが、
もうちょっと言葉や文章を正確に書いてほしい。
曖昧なところや不正確なところが多すぎて文を解釈するのに苦労するので。
一応みんなが見る掲示板だし。
0444デフォルトの名無しさん
2010/07/12(月) 00:03:58それを利用してA(N+1)を記述できる訳ではない
と言うことが解っていないのだと思う。
0445デフォルトの名無しさん
2010/07/12(月) 00:56:39Aの定義なんて、知らないよ。じゃあBB(BB(10000))を計算するには、どうすればいいわけよ。
>>444
それを利用する必要なんて、あるとは思ってないけどなぁ。
利用しようがしまいが、A(1)もA(2)もA(N)もあって、どうやって求めるのかは知らないけど、それを得ることができるのなら、
A(N+1)も得ることができるんだろ、としか思ってない。
0446デフォルトの名無しさん
2010/07/12(月) 01:15:430447デフォルトの名無しさん
2010/07/12(月) 08:25:58どうすればいい？って何を聞きたいの？
具体的にC++で記述してほしいのか？
それは無理だよ。
どんなに効率良く書いてもBB(10000)くらいの文字数が必要なんで。
BB(BB(10000)) を計算するプログラムは確かに存在するが、
それを具体的に書き表わすことは（事実上）出来ない。
当然10進数で値を知ることなど到底無理。
存在するってのは現時点のこの世の中のどこかに存在するって意味じゃなく、
考えられるすべての (有限数の) 文字の組み合わせの中に存在するって意味。
>>446
>>417 に A の定義なんて書いて無いと思うが。
単なる一時変数として使ってるだけ。
さらにその一時変数としての使い方も >>417 には2通りある。
>>425 のAの定義は
nステップ以下で停止するC++関数を停止すると判断するC++関数を A(n)とする
>>429 のAの定義は
N文字以下のすべてのC++プログラムの停止判定を行えるC++関数のうちの1個をA(N)とする
>>446 のAの定義は？
0448デフォルトの名無しさん
2010/07/14(水) 01:09:30存在しても、それを探し当てるアルゴリズムがないと計算できないんじゃない？
0449デフォルトの名無しさん
2010/07/14(水) 08:27:13計算理論で言う「計算可能」の意味ではなくて、
実際に計算して結果を得ることが出来るかって意味なら、
int main(){return 9<<(9<<99);}
この時点で無理。
0450デフォルトの名無しさん
2010/07/14(水) 10:03:38計算可能の意味だよ。
0451デフォルトの名無しさん
2010/07/14(水) 18:01:17たとえばフェルマーの最終定理が成り立つかどうかのアルゴリズムは
bool f
{
return true;
}
でもOK？
0452デフォルトの名無しさん
2010/07/14(水) 19:18:06計算理論ではアルゴリズムが存在すれば「計算可能」なので、
現実世界のリソースを用いてそのアルゴリズムを記述出来るかどうかとは無関係。
>>451
YES
0453デフォルトの名無しさん
2010/07/14(水) 21:16:22現実世界のリソースじゃなくてもいいよ。
アルゴリズムの集合の中からアルゴリズムを選び出す方法が存在することと、計算可能であることに違いはある？
0454デフォルトの名無しさん
2010/07/14(水) 22:29:35アルゴリズムの集合からアルゴリズムを選び出す方法があるかどうかにかかわらず、
アルゴリズムの存在が示されれば計算可能と言える。
そもそも、選び出す方法に対して何の限定もしなければ、
アルゴリズムの集合からアルゴリズムを選び出すのが不可能な場面なんて無い気がする。
人間じゃとても理解できない高度なアルゴリズムだって
人間じゃなければ理解できるかもしれない。
人間の能力だって人や時代によっても変わるし、
神様ならすべてお見通しかもしれない。
そんな不確定な要素に左右されないのが計算可能性の理論。
0455デフォルトの名無しさん
2010/07/15(木) 23:43:10いったい>>453の話のどこに人間が出てくるんだ？
0456デフォルトの名無しさん
2010/07/15(木) 23:52:47人間が選ばなかったらどうやってアルゴリズムを選び出すつもり？
その選び出したアルゴリズムが正しいかどうかを人間が確認しなかったら誰が確認するの？
たとえば、
>>407 が最小の奇数の完全数を返すアルゴリズム（存在すればだが）というのを
人間が確認しなかったらだれが確認するの？
アルゴリズムで確認するというなら、
その確認用アルゴリズムが正しいかどうかは誰がどうやって確認するの？
0457デフォルトの名無しさん
2010/07/16(金) 00:00:38BB(BB(10000)) を計算するアルゴリズムは存在するし、
そのアルゴリズムを選び出すアルゴリズムも存在するし。
さらにそのアルゴリズムを選び出すアルゴリズムも存在する。
しかし、選び出す方のアルゴリズムの方が選び出されるアルゴリズムより複雑で、
それらのアルゴリズムが具体的にどんなものかはだれも分からないし、
0458デフォルトの名無しさん
2010/07/16(金) 02:16:50それ言い出したら人間が計算しなければ誰が計算するんだ。
0459デフォルトの名無しさん
2010/07/16(金) 08:00:39だから『それを言いだしてもしょうがないでしょ』という説明なんだけど。
計算可能性理論では、実際に計算を行う時間や方法を考えなくて良いだけじゃなく、
実際にだれが（または何が）どうやってアルゴリズムを選ぶかも、考えなくて良い。
ただアルゴリズムが存在するかしないか、というのが計算可能性の定義。
>>453 の「選び出す方法が存在する」ってのはまさか
『アルゴリズムの集合の中からある1個のアルゴリズムを選ぶアルゴリズム』が存在する
って意味なのか？
こんなことはあまりに自明でそんなことを論じてるとは思わなかったんで、
現実世界のリソースじゃなくても良い ====> じゃあ神か何か？
と思ったんだけど。
『アルゴリズムの集合の中からある1個のアルゴリズムを選ぶアルゴリズム』に限らず、
有限の文字で表せるある1個の物を吐き出すアルゴリズムは存在する。
0460デフォルトの名無しさん
2010/07/16(金) 08:19:46たぶん質問してるのは一人じゃなくていろんなレベルの人がいる。
こっちはどういう前提で何を聞かれているのかが分からないんで
回答も適切なものにならないかもしれない。
>>448 とか >>453 は結局何が聞きたいのかいまだ良くわからない。
0461デフォルトの名無しさん
2010/07/16(金) 23:07:45(計算可能な)計算を表した文字列を引数にとり、計算の結果を返す関数。
すなわち、
f("1レスで書けるプログラムの停止可能性を求める上で十分なステップ数") = BB(BB(20000))
f("BB(BB(20000))文字以下で書けるプログラムの停止可能性を求める上で十分なステップ数") = BB(BB(BB(20000)))
なる関数。
0462デフォルトの名無しさん
2010/07/16(金) 23:32:59その関数fが計算可能かどうか？という質問？
当然関数fは計算可能ではない。
Nがある自然数の定数だとして、
"N文字以下で書けるプログラムの停止可能性を求める上で十分なステップ数"
は計算可能である。
一方、
f は N の部分にどんな自然数定数を入れても、
f("N文字以下で書けるプログラムの停止可能性を求める上で十分なステップ数") の値を返さなくてはならない。
この値は >>426 の Cstep(N) である。
f が計算可能だと仮定すると、Cstep も計算可能となって >>426 と矛盾するので、
f は計算不可能。
0463デフォルトの名無しさん
2010/07/17(土) 01:53:57> 入力として n を受け取り Σ(n) を計算するような単一のアルゴリズム A は存在しないものの（Σは計算不能なので）、n までの全ての自然数について Σ(n) を「計算」するようなアルゴリズム An は存在する
これが分からん。nは限りなく大きくできるんじゃないのか。
具体的には
A∞=lim(n->∞) An
とか
A(n)=An
ってできるだろ。
0464デフォルトの名無しさん
2010/07/17(土) 07:27:23An の n は（有限の値なら）いくらでも大きくすることが出来るが
A∞ は存在しない。
An のアルゴリズムを記述するのに（仮に）n文字以上必要だとすると、
A∞ のアルゴリズムを記述するのに有限文字じゃ出来ないよね？
∞文字必要になってしまう。
∞文字必要な物はアルゴリズムって呼ばないんで、
A∞ を計算する単一のアルゴリズムは存在しない。
0465デフォルトの名無しさん
2010/07/17(土) 09:32:36そしたら、A(n)=Anを、nが有限の値をとるものとして定義したら？
0466デフォルトの名無しさん
2010/07/17(土) 22:09:11nは初めから有限だが。
0467デフォルトの名無しさん
2010/07/18(日) 00:08:47うん。そう。
すると、>>394のいう
> プログラムの文字数が限定されていれば、
> たとえばBB(BB(10000))のような非常に大きな数による
は、どうやって十分に大きな数を選ぶんだ？
計算可能な数として存在はするが、それを選ぶことはできないんじゃないの？
0468デフォルトの名無しさん
2010/07/18(日) 07:36:02>>454 に戻ってループ？
一般的な計算理論での「計算可能」の定義は、
それを計算するアルゴリズムが存在すること。
そのアルゴリズムを選べるかどうかは無関係。
BB(BB(10000))を返すアルゴリズムは存在するのでBB(BB(10000))は計算可能。
（定義に不満なら、あなたがその道の権威者になって定義を変えてください）
じゃあそのアルゴリズムを選ぶことが出来るか？
これは誰がどうやって選ぶことを想定しているかでまったく結果が異なる。
●この世界のリソースを用いて人間が選ぶ
効率良く書いてもBB(10000)文字くらい必要なので事実上不可能。
●神が選ぶ
有限の文字数でC++で記述出来るのだから、神なら選べるんじゃないの？
●アルゴリズムが選ぶ
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムは存在する。
存在するがそのアルゴリズムを選べるかってのは誰がどうやって選ぶことを想定しているかでまったく結果が異なる。
これもアルゴリズムが選ぶ場合、
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムは存在する。
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムは存在する。
BB(BB(10000))を返すアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムを選ぶアルゴリズムは存在する。
.....
●拡張マシン
オラクル付きマシン、無限実行マシン、などチューリングマシンを超える能力のあるマシンを使えば
現実的な文字数で簡単にBB(BB(10000))を求めるプログラムが記述可能。
0469デフォルトの名無しさん
2010/07/18(日) 11:10:26つまり、計算可能なアルゴリズムの集合の中には
Nstep(1)回でプログラムが止まるかを判定するアルゴリズム
Nstep(2)回でプログラムが止まるかを判定するアルゴリズム
Nstep(3)回でプログラムが止まるかを判定するアルゴリズム
...
Nstep(BB(BB(20000)))回でプログラムが止まるかを判定するアルゴリズム
...
が含まれているから、アルゴリズムのうちの「どれか」は
1レスでのプログラムの停止判定ができる、
それがどれであるかについては、議論不要
(どうせ人には書けないし、神にとっては自明すぎるから)
、ということ？
じゃあ、任意の正の整数nを取る関数として
Nstep(n)
は、なぜ存在しない？
整数がどれだったとしても、計算可能なアルゴリズムの集合の中にはNstep(n)は含まれているのでは？
0470デフォルトの名無しさん
2010/07/19(月) 00:49:41前半は大筋ではYES
> じゃあ、任意の正の整数nを取る関数として
> Nstep(n)
> は、なぜ存在しない？
Cstep が計算不可能である簡単な証明が >>425 の【3】【4】【5】に書いてある。
> 整数がどれだったとしても、計算可能なアルゴリズムの集合の中にはNstep(n)は含まれているのでは？
これはYES
0471デフォルトの名無しさん
2010/07/19(月) 00:56:01>>425 の【3】【4】【5】は理解できるし、それが事実だというのは分かったが。
全てのnについて
λn. Nstep n
は計算可能なのに、
λn. Nstep
が計算不能というのが理解できない。
0472デフォルトの名無しさん
2010/07/19(月) 01:08:09>>1
浮動小数点数の実現方法って、処理系依存だっけ？
int main(){
float a=1.0;
while(a/2>0.0)a/=2;
return (int)(9e9/a);
}
0473デフォルトの名無しさん
2010/07/19(月) 02:17:05自然数nに対して、『Cstep(n) の値を出力するC++プログラムを書くのにn文字以上必要』だったら
『すべての自然数の入力値に対してCstepを出力する』C++関数は、有限文字じゃ書けないでしょ？
>>472
C++の規格的にはfloatやdoubleの精度や実装方法は処理系依存。
アンダーフロー時の動作も不定だったような。
ただし、このスレでは float は十分な精度があることになっており、
事実上無限の精度があると思ってもらって問題無い。
（>>34 で補足説明をしている）
この辺はintと同じ考え。
0474デフォルトの名無しさん
2010/07/20(火) 02:35:25unsigned i = 0;
while (++i);
は停止すんの？しないの？
0475デフォルトの名無しさん
2010/07/20(火) 02:58:27しないんだろ。
0476デフォルトの名無しさん
2010/07/20(火) 03:13:02enum {SET=0,MOV,ADD,CMP,JF,OP=0xf000000,R1=0xfff000,R2=0xfff};
int i,f,r[4096];
vm *p;
int e(int *c,int l) {
for (i=0; i<4096; ++i) r[i]=0;
f=i=0;p=0;
while (0 < i && i < l) {
vm *s=p,*c = new vm(*this);
int op=r[i]&OP,r1=r[i]&R1,r2=r[i]&R2;
switch(op){
case SET:r[r1]=r2;break;
case MOV:r[r1]=r[r2];break;
case ADD:r[r1]+=r[r2];break;
case CMP:f=r[r1]<r[r2];break;
case JF:i+=((r1&2)-1)*r2-1;break;
}
i++;
while(s){if(s->eq(this))return 0; s=s->p;}
p=c;
}
return r[0];
}
int eq(vm *o) {
for(int t=0;t<4096;++t) if (r[t] != o->r[t]) return 0;
return i == o->i && f == o->f;
}
};
int n(int *c,int l){int p=0;while(p<l){if(++c[p]&0xfffffff)return 1;p++;}return 0;}
int main(int ac, char *av[]){int m = 0;for (int i=0;i<999999999; ++i) {vm v;int t, *c = new int[i];for (t = 0; t < i; ++t) c[t] = 0;while(n(c, i)){t=v.e(c,i);m=(m<t)?t:m;}}return m;}
0477476
2010/07/20(火) 03:13:530478デフォルトの名無しさん
2010/07/20(火) 03:17:070479デフォルトの名無しさん
2010/07/20(火) 10:53:49無限ループと考えてもらった方が話は簡単。
そう考えてもらっても本質的差は無い。
厳密に書くと、
一応C++上はunsigned intは有限のビットで表わされ、
unsigned int の最大値に対して++をすると0になることになってるので、
言語仕様にのっとると、無限ループせずに停止することになる。
>>474 の場合はこのループがあるだけでは環境依存な値が返らないので一応問題は無い。
十分な精度とは、
たとえばBB(BB(10000))ビットなど非常に大きなサイズ以上であるということ。
（つまり事実上無限と思って問題無い程度に大きいサイズ）
この条件の元で int や unsigned int のサイズに依存しない処理を行った場合、
1レスプログラムでは決してビット数不足になることが無い。
lim n→∞ (unsigned int のbit数がnである時のmainの戻り値)
が考えられるすべての環境で存在し値が一致するプログラム
が環境依存の無いプログラムであるとしても良い。
0480デフォルトの名無しさん
2010/07/20(火) 11:07:34いくつかバグがあるみたいだが、設計の意図をくみ取って解釈してみる。
簡単な命令からなるインタープリタ言語の、
999999999未満の命令数のプログラムをすべて実行させて、
その戻り値の最大値を返すもの。
一応簡単な無限ループ検出機能があり、
過去の状態と、すべてのレジスタ、フラグ、インストラクションポインタがすべて一致したら無限ループと判断する。
インタープリタの仕様は、
レジスタが4096個 (int の中の負でない値を取りうる)
命令が以下の5個
○0〜4095の即値のレジスタへの代入
○レジスタからレジスタへの値のコピー
○レジスタにレジスタの値を加算
○レジスタ同士の大小比較を行いフラグにセット
○フラグがセットされていたら、インストラクションポインタに -4095から4095の固定値を加える
これだけあれば、本質的にC++と同じことが出来る。
0481デフォルトの名無しさん
2010/07/20(火) 11:21:27このプログラムの問題点は、正確に無限ループを判断できないこと。
たとえば以下のプログラム。
0: SET r[2], 1
1: MOV r[0], r[1]
2: ADD r[1], r[2]
3: CMP r[0], r[1]
4: JF 1
インタープリタ言語的にはr[1]が1個ずつ無限に増えていく無限ループとなっているが
これを検出出来ない。
最終的にintの上限を超えてしまって環境依存の値が返ることになる。
（intが無限精度と考えれば無限ループ）
0482デフォルトの名無しさん
2010/07/20(火) 11:25:41インタープリタのレジスタの範囲を制限して正確に無限ループを判断できるようにしたら、
今度はインタープリタのレジスタのマックス値しか作れない。
0483デフォルトの名無しさん
2010/07/21(水) 01:01:50バイトコード列の長さが有限のとき、実行する命令数に制限を作って
lp:
y = 最大x命令実行して停止するバイトコード列から得られる数の最大
if (y > x) { x = y; goto lp; }
return x;
ってした場合、停止するんかね？
0484デフォルトの名無しさん
2010/07/21(水) 02:01:03-----
lp:
y = x+1
if (y > x) { x = y; goto lp; }
return x;
-----
つまり
lim n→∞ (intのbit数がnである時のmainの戻り値)
が存在しない環境依存コード。
命令セット的には SET MOV ADD CMP JF の5個だけで十分ぽいよ。
（C++やチューリングマシンと同じ能力がある）
JFの動作が以下の間違いだと仮定しての話だけど。
× case JF:i+=((r1&2)-1)*r2-1;break;
○ case JF:if(f)i+=((r1&2)-1)*r2-1;break;
0485デフォルトの名無しさん
2010/07/21(水) 02:34:100486デフォルトの名無しさん
2010/07/21(水) 02:34:570487デフォルトの名無しさん
2010/07/21(水) 09:54:29またループになってしまって申し訳ないのだが、λn.Cstepは、
計算可能なアルゴリズム集合の中からちょうどλn.Cstep nを選び出すアルゴリズムに帰着する気がするんだが、
そういうことでいいのかな？
0488デフォルトの名無しさん
2010/07/21(水) 21:03:39n命令から成るプログラムで、
nステップ実行して 4095*pow(2,n-1) の値を返せる
MOV r[0], 4095
ADD r[0], r[0]
ADD r[0], r[0]
ADD r[0], r[0]
.....
0489デフォルトの名無しさん
2010/07/21(水) 21:43:24帰着って？
0490デフォルトの名無しさん
2010/07/22(木) 00:23:45命令数は増やさないんですよ。
0491デフォルトの名無しさん
2010/07/22(木) 01:26:58計算可能なアルゴリズム集合の中からちょうどλn.Cstep nを選び出すアルゴリズムがあれば、λn.Cstepは表現可能。
0492デフォルトの名無しさん
2010/07/22(木) 19:51:41ああ、有限じゃなくて、ある自然数以下ってことね。
ある自然数以下の長さのコードでのステップ数には当然限界があるので、
当然停止する。
で、肝心のどのくらいで停止するかをちょっと考えてみたけど、
全然大きさが見積もれない。
しばらく考えてみます。
0493デフォルトの名無しさん
2010/07/22(木) 23:39:05大きさが見積もれました。
●1回のループでのxの増加分
最大プログラム長をn命令とする。
1回のループで x が f(x, n) になるとする。
>>488 の通り、xステップでの戻り値は 4095*pow(2,x-1)以下なので、
f(x, n) ≦ 4095*pow(2,x-1) ≦ pow(4095, x)
●ループ回数
最大プログラム長をn命令とした時のループ回数を g(n) とする。
n命令以下のプログラムは
pow(0x10000000, 1) + pow(0x10000000, 2) + ... + pow(0x10000000, n)
通りである為、
g(n) ≦ pow(0x10000000, 1) + pow(0x10000000, 2) + ... + pow(0x10000000, n) ＜ pow(0x10000001, n)
●戻り値
xの初期値に対し、f(x, n) を g(n)回繰り返した値以下である。
上記より、大きく見積もっても、
4095↑↑(0x10000001↑[最大プログラム長(命令数)]) 程度であることが分かる。
※↑はべき乗、 ↑↑ はテトレーション
0494デフォルトの名無しさん
2010/07/23(金) 01:25:540495デフォルトの名無しさん
2010/07/23(金) 07:45:531命令でできる演算を2重ループしたくらいにしかならないから、
それほど大きくならない。
0496デフォルトの名無しさん
2010/07/23(金) 10:25:35pow(95, 1) + pow(95,2) + ... + pow(95,n)
通りであるため (95 = 127 - 32)、
ループ回数 g(n)≦ pow(95, 1) + pow(95, 2) + ... + pow(95, n) ＜ p(96, n)
ってそんなアホな。
0497デフォルトの名無しさん
2010/07/23(金) 20:00:29たぶんすごい勘違いをしてると思う。
0498デフォルトの名無しさん
2010/07/23(金) 21:27:321命令は6bit, レジスタは8個、命令はSUB reg, reg の1個のみです。
条件ジャンプは特定のレジスタに値を書くことで行います。
ip が負になったらプログラム終了で、-ipが返ります。
指定stepを超えたら0以下の値が返ります。
一応これだけでチューリング完全な言語になっています。
議論の手助けにでも使ってください。
int emu(int code, int step){
int reg[7] = {1}, ip = 0;
for ( ; step-- && ip >= 0 ; ip+=6){
reg[code >> ip & 7] -= reg[code >> ip+3 & 7];
if (reg[0] < 0){
ip += reg[1];
}
}
return -ip;
}
指定step数以下で停止するcode以下のプログラムの戻り値の最大値
int cmaxs(int code, int step){
int m = 0;
while (code){
int r = emu(code--, step);
if (r > m){
m = r;
}
}
return m;
}
0499デフォルトの名無しさん
2010/07/23(金) 22:10:51int cmax483(int n){
int x, y = 9;
do {
x = y;
y = cmaxs(1<<n*6, x);
} while (y > x);
return x;
}
インタープリタの命令の種類によってステップ数の増える速さが大きく変わってしまうので、
初めからstepの増加度合いを関数にしてみる。
int cmax483_(int n, int func(int)){
int x, y = 0, step = 9;
do {
x = y;
y = cmaxs(1<<n*6, step);
step = func(step);
} while (y > x);
return x;
}
>>493 と同じ方法で見積もると、
cmax483_(Ackermann(9e9999999,9), Ackermann)
とやっても、Ackermann(9,9,9)よりはるかに小さい値しか返らないというのは驚きである。
Ackermann(9e9999999,9)命令程度という、人間が組めるサイズを大きく超えたプログラム長をもってしても、
返すことの出来る値はAckermann(9,9,9)付近ではかなりスカスカであることになる。
0500デフォルトの名無しさん
2010/07/24(土) 02:45:470501デフォルトの名無しさん
2010/07/24(土) 08:59:45（とはいっても >>493 の見積もりは超えられないが）
//指定step数以下で停止するcode以下のプログラムの数を数える
int ccnts(int code, int step){
int c = 0;
while (code){
c += emu(code--, step) > 0;
}
return c;
}
//ccnts の値が増えなくなるまでstepを増やし続ける
int cmax501(int n, int func(int)){
int x, y = 0, step = 9;
do {
x = y;
y = ccnts(1<<n*6, step);
step = func(step);
} while (y > x);
return cmaxs(1<<n*6, step);
}
0502デフォルトの名無しさん
2010/07/24(土) 18:20:58どうせループ回数はcodeの取り得る値を超えられないので、
単にこれの方がマシか。
int cmax502(int n, int func(int)){
int step = 9;
for (int i = 0 ; i < 1<<n*6 ; i++){
step = func(step);
}
return cmaxs(1<<n*6, step);
}
結局cmaxsはstepより極端に大きな数は返らないので、
cmaxsを使って大きな数を作るのは厳しいか。
int main(){return emu(適当な大きな数, -1);}
とやる方が、
偶然とてつもなく大きな数が返る可能性があって、
しかも大きさを簡単に見積もれない為、夢がある分マシかも。
int a(int b,int c=9){return b*c?a(b-1,a(b,c-1)):c+9;}
int e(int c,int s){int r[7]={1},i=1;for(;s--&&i>0;i+=6)r[c>>i&7]-=r[c>>i+3&7],*r<0&&(i+=r[1]);return-i;}
int main(){return e(a(9e9999999)/a(9e999999), -1);}
0503デフォルトの名無しさん
2010/07/24(土) 18:28:16無限ループかもしれないし、とてつもなく大きな値が返るかもしれない。
現在では誰も分からない。
>>325 や >>407 と同じ分類になるのかな。
0504デフォルトの名無しさん
2010/11/02(火) 23:58:28int *max(){int *x=new int[a+1];for(int i=a;i--;)x[i]=a;x[a]=-1;return x;}
int next(int *x){while(!*x)*x++=a;if(*x==-1)return 0;(*x)--;return 1;}
void f(int *b,int *c,int *d,int *e)
{
a<<=a<<a;
if(!next(e)){e=max();
if(!next(d)){d=max();
if(!next(c)){c=max();
if(!next(b)){
return;
}
}
}
}
for(int i=a;i--;)
{
f(dup(b),dup(c),dup(d),dup(e));
}
}
int main()
{
int *b,*c,*d,*e;
b=max();c=max();d=max();e=max();
f(b,c,d);
return a;
}
0505デフォルトの名無しさん
2010/11/03(水) 00:11:34int a=9e99;
int *max(){int *x=new int[a+1];for(int i=a;i--;)x[i]=a;x[a]=-1;return x;}
int *dup(int *x){int i=0;while(x[i]==-1)i++;int **y=new int[i];i=0;while(x[i]==-1)y[i]=x[i];y[i]=-1;return y;}
int next(int *x){while(!*x)*x++=a;if(*x==-1)return 0;(*x)--;return 1;}
void f(int *b,int *c,int *d,int *e)
{
a<<=a<<a;
if(!next(e)){e=max();
if(!next(d)){d=max();
if(!next(c)){c=max();
if(!next(b)){
return;
}
}
}
}
for(int i=a;i--;)
{
f(dup(b),dup(c),dup(d),dup(e));
}
}
int main()
{
int *b,*c,*d,*e;
b=max();c=max();d=max();e=max();
f(b,c,d,e);
return a;
}
0506デフォルトの名無しさん
2010/11/03(水) 10:06:44記述ミスと思える所(dup)があるので適当に修正して大きさを見積もると、
大きさが分からないものと >>264 とを除けば
今まででダントツにデカイ。
コードも読みやすく、処理の流れも綺麗。
現段階だと文字数が多いけど、
可読性や処理の流れのきれいさを犠牲にすれば、
文字数はかなり減らせそう。
0507デフォルトの名無しさん
2010/11/10(水) 21:32:53int a=9e99;
template<class T>
void max(T *t){t=new T[a+1];for(int i=0;i<a;i++)max(t[i]);t[a]=NULL;}
void max(int *t){t=new int[a+1];for(int i=0;i<a;i++)t[i]=a;t[a]=-1;}
template<class T>
bool next(T *t){while(t&&!next(*t))max(*t++);return !t;}
bool next(int *t){while(!*t)*t++=a;if(*t==-1)return 0;*t--;return 1;}
template<class T>
T *dup(T *t){int i,j;for(i=0;t[i]!=NULL;i++);T *x=new T[i+1];for(j=0;j<i;j++)x[j]=dup(t[j]);x[i]=NULL;return x;}
int *dup(int *t){int i,j;for(i=0;t[i]!=-1;i++);int *x=new int[i+1];for(j=0;j<i;j++)x[j]=t[j];x[i]=-1;return x;}
template<class T>
void f(T *t)
{
a<<=a<<a;
if(next(t)){for(int i=a;i--;){f(dup(t));}}
}
int main()
{
int *****************************t;
f(max(t));
return a;
}
0508デフォルトの名無しさん
2010/11/10(水) 22:26:57main()
{
0509デフォルトの名無しさん
2010/11/10(水) 22:28:16{
int ******************************t;
max(t)
f(t);
return a;
}
が正しい。
0510デフォルトの名無しさん
2010/11/10(水) 23:40:11template<class T>
bool next(T *t){while(t&&!next(*t))max(*t++);return t!=NULL;}
■ このスレッドは過去ログ倉庫に格納されています