■■C++で大きな数を作るスレ■■
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2009/03/24(火) 20:27:50以下のプロトタイプの関数の戻り値で出来るだけ大きな数を返すものを作りましょう。
int main();
●ルール
最大でも１スレに収まる範囲とし、
１スレで完結したプログラムとしてください。
文字数も書いてください
●言語仕様
言語は C++ 2003 準拠とします
int と float は十分な精度があるとします
メモリは十分にあるとします
実行時間は問わないこととします
機種依存、コンパイラ依存の値が返るプログラムは不可
プリプロセッサ、ライブラリの使用は不可
●文字数カウントルール
動作上不要なコメント、スペース、タブ、改行は文字数に含めない
言語上必要なスペース、タブ、改行はカウントする（改行は１文字とする）
0333233
2009/12/19(土) 16:54:39struct Object {
Object *next;
virtual void f() {}
virtual Object *dup() { return this; }
Object **last_next(){if(next)return next->last_next();return &next;}
Object(){ next=(Object *)0;}
};
Object *o;
int a;
struct ObjectAndIntegerGrow : Object { void f(){ Object *t=o->dup(); *(o->last_next())=t; a=a<<a;} };
struct Loop : Object
{
void f(){ int *e,*p,*q,*x;
x=new int[a+1];e=x+a;
for(p=x;p<e;p++)*p=a;*p=-1;
for(;;){for(p=x;!*p;p++){
if(*p==-1)return;
for(q=x;q<p;q++)*q=a;
(*p)--;next->f();}}}
Object *dup() { Loop *l=new Loop(); if(next)l->next=next->dup(); return l;}
};
int main()
{
Object *loop;o=new Loop();a=99;
for(int i=a;i--;){loop=o->dup();*(loop->last_next())=new ObjectAndIntegerGrow();loop->f();}
return a;
}
0334デフォルトの名無しさん
2009/12/19(土) 22:02:58Loop :: f() の二重ループの中身って合ってます？
!*p の部分が１回も false にならずに
右端の -1 までたどりついて return しちゃうような気がするのですが。
0335デフォルトの名無しさん
2009/12/19(土) 22:26:34!*p の部分が１回も true にならないで無限ループ
の間違いでした。
>>233 のようにしたければ、
for(;;){
for(p=x;!*p;p++);
if(*p==-1)return;
for(q=x;q<p;q++)*q=a;
(*p)--;
next->f();
}
こうじゃないかと。
0337デフォルトの名無しさん
2009/12/19(土) 23:12:05o のチェーンの長さより a の方が大きく、
o のチェーンの長さ分 f を再帰コールしてるだけなので、
以下で良い気がする。
----------------
int a;
void f(int o){int *e,*p,*q,*x;
x=new int[a+1];e=x+a;
for(p=x;p<e;p++)*p=a;*p=-1;
for(;;){for(p=x;!*p;p++);
if(*p==-1)return;
for(q=x;q<p;q++)*q=a;
(*p)--;a<<=a;if(o)f(o-1);}}
int main()
{
a=99;
for(int i=a;i--;)f(a);
return a;
}
0338333
2009/12/19(土) 23:37:33メモリの大きさが実感しやすい形にしました。
0339333
2009/12/19(土) 23:41:150340デフォルトの名無しさん
2009/12/19(土) 23:59:34>>337 のメモリの大きさが見えにくく、
>>333 のメモリの大きさが見えにくく無い
というのが良く分からない。
どちらもとてつもなくたくさんのメモリを使うし、
使うメモリの量を調べることは、
ほとんど main() の戻り値を調べることに等しい。
というか、
チェーンが１個伸びることで、
f の再帰を意図的に１回増やすように作った訳では無いの？
loop->f() のコール前後で loop のチェーンの長さは不変なので、
f() の再帰数は loop のチェーンの長さになることは簡単にわかるのだけど。
0341333
2009/12/20(日) 00:08:54なんだか無い物のように感じてしまいます。
リストの形にすると実体が実感しやすいという、その程度のことです。
この場合、どちらも本質的に同じものであることは一応理解できます。
0342デフォルトの名無しさん
2009/12/20(日) 08:40:36>>333 に >>335 の修正を加えると、
>>233 よりはずいぶんと大きくなって、
>>233 の、n重ループ相当の巨大化操作をn回繰り返して出来た関数を
さらにループさせた感じでしょうか。
0343333
2009/12/21(月) 22:05:460344333
2009/12/22(火) 21:32:37>>335の修正を入れたプログラムがアッカーマン換算でどれくらいの大きさか教えてくらさい。
0345デフォルトの名無しさん
2009/12/22(火) 23:10:26この中に出てくる３変数アッカーマンもどきを
ループで回したくらいで,
下のより微妙に小さい位ではないかと。
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int b=99;int main(){return a(b--?main():9);} // 119
たぶんこの２つの数の間だと思う。
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int b=97;int main(){return a(b--?main():9);} // 119
int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}int b=98;int main(){return a(b--?main():9);} // 119
>>333 + >>335 で、o のLoopのチェーンが１個伸びるのと、
上の３変数アッカーマンもどきの一番左の引数b が１個増えるのが大体同じ位の効果。
0346333
2009/12/23(水) 09:05:08簡単なところから確認していっていいですか。
テーマはループと再帰、定数と自己複製ってところで。
0347デフォルトの名無しさん
2009/12/23(水) 09:09:21void f(int a) { if(a) { g() ; f(a-1) ; }}
void f(int a) { while(a--) g() ; }
0348デフォルトの名無しさん
2009/12/23(水) 09:15:48int add(a,b) { if(a) { return 1+add(a-1,b);} return b;}
int add(a,b) { while(a--) b++ ; return b; }
0349デフォルトの名無しさん
2009/12/23(水) 09:41:04勢いで書き始めちゃったけど、ちょっとまとめなおします。
しばしおまちを。
0350333
2009/12/23(水) 22:43:02ざっくりと疑問のポイントだけ書くと
（１）Loop :: f()の中の配列の長さがNならLoop :: f()の大きさは２変数アッカーマンA(N,x)と同じくらいの大きさになるんじゃないか？
（２）もしそうなら>>233の配列の大きさはN重ループと４重ループを使って、繰り返し大きくしているので
>>233自体の大きさは3変数アッカーマンのA(4,a,b)くらいになるんじゃないか？
の２点です。
どうでもいいけど、>>346で自己複製とか書いたけどただのコピーと自己複製の区別がついてませんでした。
すんませんw。
0351デフォルトの名無しさん
2009/12/23(水) 23:37:35(1) は YES.
(2) は NO.
fを関数,b,cをある定数とし、
f(x) ≒ a(b,c,x) である場合、
f をループさせた関数 f' は f'(x) ≒ a(b,c+1,x)
f を3重ループさせた関数 f''' は f'''(x) ≒ a(b,c+3,x)
>>233 の関数D は大まかには
D(x) ≒ a(x ,x) ≒ a(1,0,x) となり、
D(x) を3重ループさせて出来た関数は大まかに a(1,3,x) 位、
これをループさせで出来る a(1,4,x) よりは小さい。
0352333
2009/12/24(木) 20:26:36普通の数式ならごりごりっと展開していけば何とかなることが多いんですが、
３変数アッカーマンを展開しようとするとえらいことにｗ
なかなか手強いっす。
0353デフォルトの名無しさん
2009/12/24(木) 21:20:00int a(int b,int c=9,int d=9){return b+c&&d?a(b-!c,c?c-1:d,a(b,c,d-1)):d+9;}
a(b,c,0) = 9
a(0,0,D) = d+9
a(B,0,D) = a(b-1,d,a(b,0,d-1))
a(b,C,D) = a(b,c-1,a(b,c,d-1))
大文字の引数は1以上、小文字の引数は0以上の値とすると、
引数は上の４パターンのどれかになる。
４つめがアッカーマンの心臓部となる式である。
cを1以上の数の場合、f(x) = a(b,c-1,x) とおく。
a(b,c,0) = 9
a(b,c,1) = a(b,c-1,a(b,c,0)) = a(b,c-1,9) = f(9)
a(b,c,2) = a(b,c-1,a(b,c,1)) = a(b,c-1,f(9)) = f(f(9))
a(b,c,3) = f(f(f(9)))
a(b,c,4) = f(f(f(f(9))))
となる。
つまり、a(b,c,x) は a(b,c-1,x) をループさせて出来る関数になる。
0354デフォルトの名無しさん
2009/12/24(木) 21:42:34では次に1個目の引数bについて考えてみる。（とりあえずbを固定して考える）
３つ目の式の出番である。
a(3,c,x) を考える。
a(3,c,x) はcが大きくなればどんどん増大度が増えていく。
ところが、いくらcが大きくても、a(3,x,x) にはいずれ抜かれることになる。
（実際、xがc を超えれば、a(3,c,x) < a(3,x,x) となることがわかる）
a(3,x,x) でなくて、たとえば a(3,x,1) でも大した差はなく、
a(3,c,x) をいずれ抜くことになる。
つまり、a(3,x,1) は a(3,0,x) を固定回ループさせて作ったどんな関数よりも増大度が大きい。
a(4,0,x) を考えてみる。
式3によると、xが1以上の時、
a(4,0,x) = a(3,x,a(4,0,x-1)) ≧ a(3,x,9)
となるので、a(3,0,x) を固定回ループさせて作った関数よりも増大度が大きい。
0355デフォルトの名無しさん
2009/12/24(木) 21:44:56a(B,0,D) = a(b-1,d,1)
や
a(B,0,D) = a(b-1,d,d)
で十分なのだが、
４つ目の式となるべく共通化した方が文字数が減らせるので
a(B,0,D) = a(b-1,d,a(b,0,d-1))
となっている。
0356333
2009/12/25(金) 22:28:184変数はこれで良いですか？
A(0,0,0,d)=d+9
A(a,b,c,0)=A(a,b,c-1,1)
A(a,b,0,d)=A(a,b-1,d,d)
A(a,0,0,d)=A(a-1,d,d,d)
A(a,b,c,d)=A(a,b,c-1,A(a,b,c,d-1))
0357デフォルトの名無しさん
2009/12/26(土) 08:57:32良いと思います。
0358333
2009/12/27(日) 00:20:39ありがとうです。
>>353の展開の仕方がわかりやすかったです。
きれいな構造ですね。
a(b,x,y)=f(x,y)とおいてf(N,1)を展開すると
f(N,1)=f(N-1,f(N-2,f(N-3,f(N-4,...f(0,1)))...)
となるようでこれもまたきれいな構造です。
この構造をどう解釈すればいいのかはよくわからないですが…
0359333
2010/01/14(木) 20:08:38int *dup(int *x){
int *p,*q;
p=x;while(*p++!=-1);
q=new int[p-x];p=q;while(*x!=-1)*p++=*x++;*p=*x;
return q;
}
void f(int *x){
int *y;
a<<=a<<a;
if(*x==0){
y=x;while(!*y)*y++=a;if(*y==-1)return;
(*y)--;f(x);
}
else{
for(int i=a;i--;){
*y=dup(x);y[0]--;f(y);
}
}
}
int main()
{
int *x;
for(int i=a;i--;)
{
x=new int[a+1];
for(int j=0;j<a;j++)x[i]=a;x[a]=-1;
f(x);
}
return a;
}
0360デフォルトの名無しさん
2010/01/14(木) 21:35:17おっと、一気に大きくなりましたね。
>>259 の 138文字のよりも大きくて、
138文字のを 9e99 回ループさせたくらいでしょうか。
--------
ちなみに、138文字のはもうちょっと縮んで131文字になりました。
int a=9;struct b{int c,d;b*e;void operator*(){b f={c-!d,d?d-1:++a,e},g=f;g.e=&f;if(e)**e;if(c+d)*g;}}c={a};int main(){*c;return a;} // 131文字
0361デフォルトの名無しさん
2010/01/17(日) 02:09:19がんばって >>359 を極限まで縮めてみました。
>>360 とほとんど同じ値になるのですが、
3文字届きませんでした。
( >>360 も限界と思ったところから 7文字縮めたので、さらに縮められるかもしれません)
>>192 もそうですが、
だいたい同じ値をまったく異なる発想で作って、
だいたい同じ文字数になっているのがおもしろいです。
// 134
int a;
struct b{
int c[9],*d;
void operator*(){
b e=*this;
d=e.c+9;
for(;--*--d<0?*d=++a,d!=e.c:(*e,*e,0););
}
}c={9};
int main(){
*c;
return a;
}
0362デフォルトの名無しさん
2010/01/17(日) 02:18:30int c[9],*d;
じゃなくて
int*d,c[9];
にしたら1文字縮まりました。
あと2文字。
0363デフォルトの名無しさん
2010/01/17(日) 02:25:55取り消します。
>>362 だと
}c={9};
のところを
}c={0,9};
にする必要があるので、逆に長くなっちゃいますね。
0364デフォルトの名無しさん
2010/01/18(月) 00:38:048文字縮めました。
これで >>360 を抜いてこのクラス最短に。
// 126文字
int a;
struct b{
int c[9],*d;
void operator*(){
b e=*this;
for(d=e.c+9;d>e.c;--*--d>0?*e,0:*d=++a);
}
}c={9};
int main(){
*c;
return a;
}
0365デフォルトの名無しさん
2010/01/18(月) 21:16:57int a;struct b{int c[9],*d;void e(){b f=*this;for(d=f.c+9;d>f.c;--*--d>0?f.e(),0:*d=++a);}}c={9};int main(){c.e();return a;} // 124
>>192 を2文字縮めて76文字
>>83 の77文字を抜いてこのクラス最短に
int a,b[9]={9},*c=b;int main(){for(;c>=b;--*c>0?c=b+8,0:*c--=++a);return a;} // 76
0366デフォルトの名無しさん
2010/02/25(木) 07:34:47>>83 の77文字のが縮まって64文字に
なりました。
0367デフォルトの名無しさん
2010/06/05(土) 11:34:17短い順にすべての文字列の組み合わせを順番に全部インタプリタで食わせてみて
同じ文字数で最も大きい値を返すプログラムになってるものを採用すればいいんじゃね?
と思ったが停止判定ができないから不可能なのか。
0368デフォルトの名無しさん
2010/06/08(火) 19:34:56ステップ数====>戻り値
はそれほど大きな関数には成り得ないから
ステップ数で制限しちゃうと全然大きくならないし。
0369デフォルトの名無しさん
2010/06/24(木) 00:37:28こういうのじゃだめなのか43文字
int main()
{return (((unsigned int)0)-1)/2;}
0370デフォルトの名無しさん
2010/06/24(木) 23:47:23>>1-368
0371デフォルトの名無しさん
2010/06/25(金) 20:31:32もろに >>2 のダメな例に書いてあるし。
しかも >>2 よりも長い。
0372デフォルトの名無しさん
2010/06/26(土) 13:08:14これ本当かなあ。「1レスで作れる最大の数」が定義できたと仮定すると、
リシャールのパラドックス的なことをして矛盾を導ける可能性はないの?
ビジービーバー関数みたいに定義はできるけど計算不可能だから
プログラムには書けない、ということで矛盾しないのかな?
0373デフォルトの名無しさん
2010/06/26(土) 16:04:23int main(){return pow(a(9,9),a(9,9));}
と
int a(int m,int n){return (m)?(n)?a(m-1,a(m,n-1)):a(m-1,1):n+1;}
int main(){return a(9999999,9999999);}
はどっちが大きいんだ（文字数は同じ）
0374デフォルトの名無しさん
2010/06/26(土) 16:19:080375デフォルトの名無しさん
2010/06/26(土) 16:21:290376デフォルトの名無しさん
2010/06/26(土) 16:51:23int main(){return a(a(9,9),a(9,9));}
のほうが圧倒的に大きくて文字数も少ない
大雑把に言ってpow(x,x)はa(4,x)にも勝てない
0377デフォルトの名無しさん
2010/06/26(土) 19:44:190378デフォルトの名無しさん
2010/06/26(土) 20:54:16別に矛盾しないだろ。
1レスの文字数上限が決まっているので、
1レスで作れるプログラムも有限個しかない。
その中の >>1 の条件に当てはまるものの戻り値の最大値
が「1レスで作れる最大の数」になる。
>>1 のように適切に言語を制限すればベリーのパラドックスは発生しない。
（ISO/IEC 14882:2003 という言語に曖昧な部分が無いという仮定 は必要）
その最大値がどのくらいの大きさの数かを知るすべは無いとは思うが。
0379デフォルトの名無しさん
2010/06/26(土) 20:58:56たとえば
int main(){int i=0;for(;;)++i;return i;}
みたいなプログラムは停止しないから(明記されてないけどたぶん)ルール違反でしょ?
ということは1レスで作れる最大の数を定義するには
1レスで書けるプログラム全てに対して停止判定ができなきゃいけないと思うんだけど。
停止判定ができないのはプログラムサイズに上限を付けなかった場合で
任意の有限サイズ以下のプログラムに対する停止判定だったら原理的には
可能なんだっけ?
0380デフォルトの名無しさん
2010/06/26(土) 21:19:43その関数を使ったプログラムを書いて矛盾を導くから、
h(x,y)が1レスでは決して書けないことを証明できれば
1レスで書けるプログラム全てに対してh(x,y)で停止判定ができても矛盾しない。
0381デフォルトの名無しさん
2010/06/26(土) 21:37:01少なくともh(x,y)が書けたら停止判定できないことは証明されてるけど、
h(x,y)さえなければ停止判定できることって証明されてたっけ？
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) が存在する』も当然成り立つ
■ このスレッドは過去ログ倉庫に格納されています