■■C++で大きな数を作るスレ■■
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2009/03/24(火) 20:27:50以下のプロトタイプの関数の戻り値で出来るだけ大きな数を返すものを作りましょう。
int main();
●ルール
最大でも１スレに収まる範囲とし、
１スレで完結したプログラムとしてください。
文字数も書いてください
●言語仕様
言語は C++ 2003 準拠とします
int と float は十分な精度があるとします
メモリは十分にあるとします
実行時間は問わないこととします
機種依存、コンパイラ依存の値が返るプログラムは不可
プリプロセッサ、ライブラリの使用は不可
●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
0382デフォルトの名無しさん
2010/06/26(土) 21:37:39もっともっといじると、>>197 の80文字にまで縮まる。
>>376 よりは微妙に大きい。
>>377
いままで私が把握してる中では、
64文字〜135文字、140文字〜148文字はすべてアッカーマン関数やその拡張を使った記録が続いている。
（136文字〜139文字は >>259の考えを使ったもの）
アッカーマン圧巻！
単に私の知識や発想が狭いからそうなっちゃってるという可能性も否定はできないが....
0383デフォルトの名無しさん
2010/06/26(土) 21:49:01停止判定出来ようが出来まいが、
無矛盾に値を定義することはできる。
値を返すプログラムがどのようなものかを調べるアルゴリズムが存在するかどうか
という命題とは関係無しに。
で、そのアルゴリズムが存在することも簡単にわかる。
単に十分大きな値で停止判定すれば良い。
でその十分大きな値というのがどの程度大きな値であるか
を調べるアルゴリズムが存在するかどうかはわからない。
値を調べるアルゴリズムが存在するかどうかはわからないが、
停止判定を行うのに十分な大きな値が存在するということはわかる。
0384デフォルトの名無しさん
2010/06/26(土) 21:49:58すべてのプログラムは停止するかしないかのいずれかだから、
1レスで書けるプログラムすべてを表に登録して、表引きで停止するかしないか
返すプログラムを書けば判定できる。
その表をどうやって作るんだと言われても知らないけど表の長さが有限であることさえ
示せばプログラムが存在することは確か(判定したいプログラムの長さに上限がなければ
表も有限にならないのでダメ)。
0385デフォルトの名無しさん
2010/06/26(土) 22:08:54停止判定ができるなら>>367みたいなプログラムが実際に存在するということだから
int a(){/*1レスで書ける最大値を計算するプログラム*/}
int main(){return a()+1;}
が1レスに収まるなら矛盾する。だから無矛盾に定義するには
停止判定ができないか、>>367みたいなプログラムは十分短く書けないことを
証明する必要がある。
0386デフォルトの名無しさん
2010/06/26(土) 22:16:25後半２行、
ある証明で用いたテクニックが使えない ===> 無矛盾
というのは無理がありすぎる。
----
具体的に1レスで収まるプログラムの停止判定アルゴリズムを示すと、
1レスで記述できるプログラムをすべて列挙する。
この中で、N※ ステップ以内に停止しないものを除く。
さらに、プログラム終了までの間に環境依存な動作を行ったプログラムを除く。
残ったプログラムの戻り値のうちの最大のものが求める数。
※ Nは十分大きな整数。
（1レスで記述出来るプログラムの最大ステップ数以上であればなんでも良い）
0387デフォルトの名無しさん
2010/06/26(土) 22:29:51『Nは十分大きな整数』で気に入らないなら、
N = BB(BB(10000)) とかに決めても良いよ。
0388デフォルトの名無しさん
2010/06/26(土) 22:33:53『値が定義出来る』と
『値を求めるアルゴリズムが存在する』と
はまったく別ものなんだよね。
>>372 の疑問からなぜ『値を求めるアルゴリズムが存在するか』にすり変わったのかがわからない。
0389デフォルトの名無しさん
2010/06/26(土) 23:37:29> 定義はできるけど計算不可能だからプログラムには書けない
0390デフォルトの名無しさん
2010/06/28(月) 19:45:43> ビジービーバー関数みたいに定義はできるけど計算不可能だから
> プログラムには書けない、ということで矛盾しないのかな?
プログラムに書けない ====> 矛盾
の理屈がわからないのだけど....
0391デフォルトの名無しさん
2010/06/29(火) 02:26:02>>372には『「1レスで作れる最大の数」が定義できたと仮定すると』って書いてあるよ。
そう仮定したとき、その最大の数を求めるプログラムを1レスで書けなければ仮定と矛盾するんじゃない？
0392デフォルトの名無しさん
2010/06/29(火) 19:08:53「1レスで作れる最大の数」の定義は、
1レスプログラムを用いて定義する訳じゃないので
何も矛盾しない。
以下は21文字以内で作れるプログラムの中で（おそらく）最大の数を返すが、
int main(){return 9;}
int main(){return+9;}
このプログラム自身は21文字以内で最大であることを示してもいないし、
21文字以内で作れるプログラムの中での戻り値の最大値を探すものでもない。
またおそらく21文字ではそのようなプログラムは作れないし、
（文字数を限定せずに）そのようなプログラムを作れるかどうかは、
最大の数を定義できることとは別の問題。
0393デフォルトの名無しさん
2010/06/30(水) 00:22:18それが本当に最大かどうかを確認する最も愚直な方法は、
21文字以内で表現できうるプログラムを全て実行させてみることだけど、
その中に計算が、T秒以内に終わらない可能性もあるわけだろ。
(まぁ、Tが十分大きければ21文字ではないだろうが。)
そのT秒以内に終わらないプログラムが、最大の整数を返すプログラムでないことを示す方法はある？
止まらなかったら2*T秒動かしてみる、というのも手だけど、それだと無限ループに引っかかる。
1レス以内に書けるプログラムに限定して、停止問題を解くことができるか、という話はそこらへんから出てきてる。
停止判定ができるのなら、有限時間に終わるプログラムのみを実行して、最大の整数を確認すればよい。
0394デフォルトの名無しさん
2010/07/01(木) 12:41:37（文字数を限定しなければ）プログラムすべての停止判定を行うことができるアルゴリズムは存在しない
プログラムの文字数が限定されていれば、
たとえばBB(BB(10000))のような非常に大きな数による
ステップ数制限を使った停止判定が行える。
よって返すことが出来る最大の数を調べるアルゴリズムも存在する。
（アルゴリズムが存在するというだけで、実際に動作してみて結果を得ることは事実上無理）
プログラムの文字数が限定されていなければ、
すべてのプログラムの停止判定を行うことができる単一アルゴリズムは存在しない。
0395デフォルトの名無しさん
2010/07/03(土) 00:14:40それをするには、ステップ数の上限を決めないといけないわけだろ。
そんなの、どうやって決める？
0396デフォルトの名無しさん
2010/07/03(土) 07:22:49『たとえばBB(BB(10000))』と書いてあるが。
0397デフォルトの名無しさん
2010/07/03(土) 12:59:27それは本当に十分なの？
0398デフォルトの名無しさん
2010/07/04(日) 01:52:02YES.
（数学的に厳密な証明は私には出来ないが、意味を考えれば十分すぎる値）
また、仮に不十分であったとしても、
『ある文字数以内のプログラムすべての停止判定を行うことが出来るアルゴリズムは存在する 』
を否定することにはならない。
nステップ以内で止まるプログラムを停止するプログラムと判断するアルゴリズムをA(n)とするとき、
A(1), A(2), A(3), ..... の中に上記アルゴリズムが存在することは確かな訳で。
0399デフォルトの名無しさん
2010/07/04(日) 22:22:30厳密な証明でなくてもいいから、なんでそれが十分といえるのか。
> nステップ以内で止まるプログラムを停止するプログラムと判断するアルゴリズムをA(n)とするとき、
> A(1), A(2), A(3), ..... の中に上記アルゴリズムが存在することは確かな訳で。
存在するが、その計算は有限時間で終わるのか。
すなわち、全てのM>0に対して
A(1) && A(2) && ... && A(N) == A(1) && A(2) && ... && A(N) && A(N+1) && ... && A(N+M)
を満たすNを有限時間で求めることはできるか。
これは、停止アルゴリズムの存在の必要十分条件になってる。
0400デフォルトの名無しさん
2010/07/04(日) 23:59:521レスに記述できるプログラムは1E100ビットで保存出来る。
チューリングマシン語1ステートで（少なくとも）1ビットの情報を
テープに書くことが出来るので、
チューリングマシンのテープに任意の1レスプログラムを書く為に
1E100ステートあれば十分。
C++をステップ実行出来るプログラムは世の中にあり、
チューリングマシン語も（当然ながら）チューリング完全であって
世の中のコンピューター言語と本質的に同じことが出来るので、
C++のプログラムをステップ実行して終了までのステップ数を数えるような
チューリングマシンのプログラムを書くことが可能。
コンピューター言語とチューリングマシン語の記述効率がどの程度差があるかはわからないが、
それほど大きな差はないはずで、
少なくとも1E100ステートあれば十分記述は可能である。
以上より、1レスプログラムのステップ数を数えて、そのステップ数を
HALT時のテープ上の1で返すようなプログラムを
チューリングマシン語2E100ステートで記述することが可能である。
（終了しないプログラムに対してはどんな動作でも構わない）
1レスで書ける、停止するプログラムの中で最大ステップ数の物に対しても
2E100ステートでステップ数を返せることになるので、
BB(n) の定義よりこのステップ数はBB(2E100)以下であることが分かる。
（当然BB(BB(10000))以下）
0401デフォルトの名無しさん
2010/07/05(月) 00:10:533行目以降は意味が良くわからない。
A(i) は iステップまでしか調べないのだから当然有限時間で停止する。
（そもそも有限時間で停止しないようなものはアルゴリズムとは言わない）
A(i) が
『ある文字数以内のプログラムすべての停止判定を行うことが出来るアルゴリズム』
となる i を有限時間で見つけられるか？
という意味であればそれはもう
『ある文字数以内のプログラムすべての停止判定を行うことが出来るアルゴリズムは存在する 』
という命題とは別の問題にすり変わっている。
0402デフォルトの名無しさん
2010/07/05(月) 00:59:30うん。そりゃ、iステップ目までしか調べないのだから、停止する。
が、それではi+1ステップ目で停止するプログラムを見逃すことになる。
それを見逃さないアルゴリズムは
『ある文字数以内のプログラムすべての停止判定を行うことが出来るアルゴリズム』
と等価。
>>400
ダウト。
(i) 明らかに、プログラムの文字数から、プログラムを保存するのに十分なビット数を求めるアルゴリズムは存在し、その値は有限になる
(ii) >>400により、プログラムを保存するのに十分なビット数が求まれば、そのプログラムの最大ステップ数を求めることができる
(iii) 最大ステップ数が求まれば、明らかに有限時間で停止判定ができる
これらより、任意の有限文字数のプログラムで停止判定が行えるということ結論が得られるが、
これは明らかにチューリングの停止判定不能問題に矛盾。
0403デフォルトの名無しさん
2010/07/05(月) 02:13:11前半
i+1ステップ目で停止するプログラムを見逃すことはなんら問題が無い。
十分大きな i (たとえばBB(BB(10000)) ) を選べば、
1レスで記述できるC++の（停止する）プログラムのステップ数は
i 以下になるのだから。
後半
「任意の i に対し BB(i) を得ることが出来る」アルゴリズムは存在しない
よって、単一アルゴリズムで (ii) が実現出来ない
0404デフォルトの名無しさん
2010/07/05(月) 02:25:48BBが何なのか知らん(IEEEの論文から検索かけても見つからん)が、
任意のiでなくてもいいよ。十分に大きければ。
0405デフォルトの名無しさん
2010/07/05(月) 02:37:52> コンピューター言語とチューリングマシン語の記述効率がどの程度差があるかはわからないが、
> それほど大きな差はないはずで、
これ怪しいね。
ステップ数に対して指数関数的に増加する可能性を否定するだけでも一苦労だと思うよ。
0406デフォルトの名無しさん
2010/07/05(月) 02:44:30>>398を読み直せば、ここではBB(BB(10000))が十分大きいとみなせないことが分かる。
0407デフォルトの名無しさん
2010/07/05(月) 14:11:09int p(int n)
{
int i, s = 0;
for (i = 1; i < n; i++)
if (n % i == 0) s += i;
return s == n;
}
int main()
{
for (int n = 1; ; n += 2)
if (p(n)) return n;
}
0408デフォルトの名無しさん
2010/07/05(月) 19:10:09BB(n) ビジービーバー関数
Σ(n) と書いた方が良かったか
>>405
初期のマイコンのアセンブラレベルのインタープリタなら比較的簡単に作れる。
これを用いれば、より記述効率の良いインタープリタが作れる。
それを用いてC++のインタープリタが作れる。
それほど大きな差はないはずだという根拠はこれだ。
1E100ステートあれば十分すぎる。
>>406
BB(BB(10000))じゃ十分じゃないというなら
証明、解説をしてくれ。
0409デフォルトの名無しさん
2010/07/05(月) 19:20:41ひさびさにC++のコードが。
これは無限ループなのか値を返すのかが、まだ人類のだれも分かってないもの。
仮に値を返すとしてもどのくらいの値が返るかもわからない。
発想としては >>325 と同じ。
だれも無限ループなのか値が返るのかわからないコード。
可能性的には、とてつもなく大きな値を返すかもしれない。
0410デフォルトの名無しさん
2010/07/05(月) 19:48:56途中で同じ計算繰り返すことになって
無限ループ突入だろ
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インタープリタのレジスタの範囲を制限して正確に無限ループを判断できるようにしたら、
今度はインタープリタのレジスタのマックス値しか作れない。
■ このスレッドは過去ログ倉庫に格納されています