自然数0,1,2,3,...各々に対して
より少ない命令数でこれらを出力するアルゴリズムを探索していくスレです
使える命令は3つだけ
inc xi 変数xiの値を1増やす
dec xi 変数xiが0でなければ値を1減らす
jz xi,l 変数xiが0ならば、l番目の命令に飛ぶ
参考:http://en.wikipedia.org/wiki/Counter_machine
変数は0より大きな整数を格納でき、初期値として0が入っています
変数はx0,x1,x2,…の可算無限個を使用できます
最後の命令がジャンプせずに実行されるか、命令数より大きな行番号にジャンプすればプログラムは終了します
プログラム終了時、x0に入っている値をプログラムの出力値とします
・変数名は好きにつけ変えて良い(どれが出力用の変数x0かは明示する)
・jz, *loop などのように行番号ではなくいわゆるラベルを使って良い
・曖昧性がなく分かりやすいならば独自の記法をしても良い
・他のプログラムを関数と見立てて使用してよい(ただし再帰呼び出しは(多分)出来ない)
(補足を踏まえた例)2nを出力する命令数n+5のプログラム
inc x
inc x
fortimes_clr(x){
inc result
:
(n回)
:
inc result
}
ここで
fortimes_clr(x){
<命令列hoge>
}
を次のように定義する
*loop jz x, *out
dec x
<命令列hoge>
j *loop
*out
jは無条件ループ(適当な利用していない変数を使えば実装できる)
<変数xにaを加算する命令数n1の処理>
*loop jz, x, *out
<変数yにbを加算する命令数n2の処理>
dec x
j, *loop
*out
この処理で変数yにbがa回足されるためy:=y+a*bが計算される
incによる加算、decの減算、そしてこの乗算の処理を組み合わせて
最小命令数で自然数を構成する(*)
上記の方法(*)を使って、最小の命令数kで構成できる自然数の集合をN(k)とする
N(k)は再帰的に構成できる
N(0) = { 0 }
N(k+1) = { n+1 | n∈N(k) }∪{ n-1 | n∈N(k), 0<n }∪( ∪[i=0,k-2]{m*n|m∈N(i),n∈N(k-2-i)} )＼∪[i=0,k]N(k)
方法(*)を用いた時の最小の命令数が各自然数ごとに計算できます
0から100までの命令数を、自然数(命令数)の形式で示します
0(0), 1(1), 2(2), 3(3), 4(4), 5(5), 6(6), 7(7), 8(8), 9(9), 10(10), 11(11), 12(10), 13(11), 14(12), 15(11), 16(11), 17(12), 18(12), 19(13),
20(12), 21(13), 22(14), 23(14), 24(13), 25(13), 26(14), 27(15), 28(14), 29(15), 30(14), 31(15), 32(15), 33(16), 34(16), 35(15), 36(15), 37(16), 38(17), 39(17),
40(16), 41(17), 42(16), 43(17), 44(18), 45(17), 46(18), 47(18), 48(17), 49(17), 50(18), 51(18), 52(18), 53(19), 54(18), 55(19), 56(18), 57(19), 58(20), 59(19),
60(18), 61(19), 62(20), 63(19), 64(18), 65(19), 66(20), 67(20), 68(19), 69(20), 70(20), 71(20), 72(19), 73(20), 74(20), 75(19), 76(20), 77(21), 78(20), 79(20),
80(19), 81(20), 82(21), 83(21), 84(20), 85(20), 86(21), 87(21), 88(21), 89(21), 90(20), 91(21), 92(21), 93(21), 94(22), 95(21), 96(20), 97(21), 98(22), 99(21), 100(20)
括弧内の数字は方法(*)以外の方法を使った時より小さい値にできるかもしれません
(大きな数では指数計算も使った方が命令数を削減できるでしょう)
目下の目標としては
括弧内の数字以下の命令数で自然数を構成できればと思います
探してみたけど見つからんかった
突貫工事で作ってみました
CounterMachineシミュレータ
http://www1.axfc.net/uploader/Sc/so/179776.zip&key=cm
jはjzの書き間違いとしても，0じゃないからジャンプしないよ．
例えば jz x_tmp, *loop
等とすれば *loop への無条件ジャンプ命令が実装できます
いちいち …x_tmp… と書くのは面倒なので j *loop と書いています
<変数xにa-1を加算する命令数n1の処理>
*loop<変数yにbを加算する命令数n2の処理>
jz, x, *out
dec x
j, *loop
*out
の方が短くなる．例えば10は
inc x
inc x
inc x
inc x
// loop
inc x_0
inc x_0
quit x
dec x
j //loop
でjumpのラベル//loopを除いて9命令．
(Where quit x:= jz x,最後の命令より後の行)
a-1とbの生成方法を用いてabを構成するのと同じ長さで
abより小さいいくつかの数を構成できる．
例えば47は
inc x
inc x
inc x
inc x
inc x
//loop
inc x_0
inc x_0
inc x_0
inc x_0
inc x_0
inc x_0
inc x_0
quit x
inc x_0
dec x
j //loop
で48と同じ16で出力できる．
inc x
...
inc x ← n times
//loop1
inc y
//loop2
inc x_0
jz x,//soto
dec x
j //loop1
//soto
quit y
dec y
j //loop2
長さはn+8で，例えば49は15で出力できる．
>>12と同様に考えて長さn+8のn(n+1)バージョンもある．
これの//loop2のすぐ下のinc x_0の数を2つにすると，
2(n+1)^2や2n(n+1)をn+9で出力できる．
例えば98は16．
inc x
...
inc x ← n times
これはバカみたいだ．nを生成する最短手順に訂正．
最短手順数をl(n)とおくと>>13のアルゴリズムはl(n)+8，etc.
inc x
...
inc x ← n times
//loop1
inc x_0
jz x,//soto
inc y
dec x
j //loop1
//soto
quit y
//loop2
inc x
dec y
jz y,//loop1
j //loop2
とかにしてl(n)+10でn(n+1)/2かな．あんまり美味しくない．
つまり >>2で述べたようなfortimesループの実装で
ループから抜けるための命令(>>12で言うquit)の位置を一般化することで
同じ命令数3のfortimesループでも処理に幅を持たせられるわけですね
<x1にaを加算する命令数saの処理>
*loop
<x0にbを加算する命令数sbの処理> …処理(b)
jz x1, *out
<x0にcを加算する命令数scの処理> …処理(c)
dec x1
j *loop
*out
と書けば
処理(b)がa+1回、処理(c)がa回実行されるので、全体として
"x0に(a+1)*b+a*c"を加算する命令数sa+sb+sc+3の処理"を
していることになりますね…(*')
b=0の場合が>>2のfortimesにあたります
inc、dec、そして >>16の(*') の処理の組み合わせの最小命令数で
自然数を構成しました
>>5に比べて命令数は少なくできました
・自然数(命令数)の表
0(0), 1(1), 2(2), 3(3), 4(4), 5(5), 6(6), 7(7), 8(8), 9(8), 10(9), 11(9), 12(9), 13(10), 14(10), 15(10), 16(10), 17(11), 18(11), 19(11),
20(11), 21(12), 22(12), 23(12), 24(12), 25(12), 26(13), 27(13), 28(13), 29(13), 30(13), 31(14), 32(14), 33(14), 34(14), 35(14), 36(14), 37(15), 38(15), 39(15),
40(15), 41(15), 42(15), 43(16), 44(15), 45(15), 46(16), 47(16), 48(15), 49(16), 50(16), 51(16), 52(16), 53(17), 54(16), 55(16), 56(16), 57(16), 58(17), 59(17),
60(16), 61(17), 62(17), 63(17), 64(16), 65(17), 66(17), 67(17), 68(17), 69(17), 70(17), 71(18), 72(17), 73(18), 74(18), 75(17), 76(17), 77(18), 78(18), 79(18),
80(17), 81(18), 82(18), 83(18), 84(18), 85(18), 86(19), 87(18), 88(18), 89(19), 90(18), 91(19), 92(18), 93(19), 94(19), 95(18), 96(18), 97(19), 98(19), 99(19), 100(18)
そういうことです．どうも．
48は4×12の方が6×8より短いのですね．
これって，一種のコルモゴロフ複雑性のようなものを求めている，ということなんですかね．
だと思います。つまり計算不能。
大きな値になるとアルゴリズムは無限に複雑になってきます。
ある自然数を構成するアルゴリズムについて
それが最小命令数であることの証明が出来ないものも出てきます。
このスレではちょっとしたパズルとして
値の更新をちまちまやっていければと思っています。
今までのレスや、プログラムの命令に関して分かりにくいところがあれば
質問受付ます。
今見返すと、自分でも分かりやすく説明できているとはあまり思えませんので。
add xi, n
とかにしても良いし、
条件分岐とくっつけて、addjz xi, n, l
の1種類の命令でも良いはず。
なぜその3種を選んだのか？
0である変数をdecした場合、
0のままなのか、値不定なのか、動作不定なのか、
こんな単純な3種の命令で未定義動作があるのも理解不能。
そもそも、
チューリングマシンという1種類の命令のみからなるマシンが1937年に作られているのに、
別の命令体系にする意味もよくわからん。
少ない命令数でどれだけ大きな数が作れるのだろうかと。
7命令まではincを命令数分連ねるだけ
8命令からは、複数個のincをループすることで掛け算相当
15命令からは、掛け算相当をさらにループにすることで指数関数相当
15: 126
16: 510
17: 2331
18:13995
19:88572
20命令で、指数関数相当をさらにループにすることでテトレーション相当
20: 2^2^2^3-4
21: 2^2^2^2^3-4
...
26命令以降、テトレーションをさらにループすることでペンテーション相当
26: >2^^255
アルゴリズムが複雑になるのはこの後
26命令でスタック、再帰呼び出しの動作を入れることで
有名な急増加関数が作れる。
ただし、瞬発力がそれほど高くないので、
ペンテーションによる実装を超えるのは30命令
46以降かなりの率で >>17 より減らせる。
3～4つ減らせるのもある。
73(15), 74(15), 78(15), 84(15), 93(16), 94(15)
なにか大きな勘違いをしてる？
そーすうp
11(9), 12(9), 13(10), 14(10), 15(10), 16(10), 17(11), 18(11), 19(11), 20(11),
21(12), 22(12), 23(12), 24(12), 25(12), 26(13), 27(13), 28(13), 29(13), 30(13),
31(14), 32(14), 33(14), 34(14), 35(14), 36(14), 37(15), 38(15), 39(15), 40(15),
41(15), 42(15), 43(15), 44(15), 45(15), 46(15), 47(15), 48(15), 49(15), 50(15),
51(15), 52(15), 53(15), 54(15), 55(16), 56(15), 57(15), 58(16), 59(16), 60(15),
61(16), 62(15), 63(15), 64(15), 65(15), 66(15), 67(16), 68(16), 69(16), 70(16),
71(16), 72(16), 73(15), 74(15), 75(16), 76(16), 77(16), 78(15), 79(16), 80(16),
81(16), 82(16), 83(16), 84(15), 85(15), 86(16), 87(16), 88(16), 89(16), 90(16),
91(16), 92(16), 93(16), 94(15), 95(15), 96(16), 97(16), 98(17), 99(16), 100(16),
> 0のままなのか、値不定なのか、動作不定なのか、
これは >>1 に載ってました。 0のまま。
これも利用できるかも。
実は、 >>17 の82(18) と 83(18) がどうやったか気になってる。
83(18) は 4*5*5+3 で出来るけど、
82(18) は掛け算方式でやる方法がわからない。
6*16の5*16が終わったあとに2を足したところで抜ける(cf.>>11)ようにすればよいのでは。
それよりソースうｐ。
+2
+2
+2
+2
+2
+2
-2
+1
+1
+1
+0
+0
/2 20
+0
+0
/1 6
-1
/9 10
で実現できるよ。
11(9), 12(9), 13(10), 14(10), 15(10), 16(10), 17(11), 18(11), 19(11), 20(11),
21(12), 22(12), 23(12), 24(12), 25(12), 26(13), 27(13), 28(13), 29(13), 30(13),
31(14), 32(14), 33(14), 34(14), 35(14), 36(14), 37(14), 38(14), 39(14), 40(14),
41(14), 42(14), 43(14), 44(14), 45(14), 46(14), 47(14), 48(15), 49(14), 50(14),
51(15), 52(14), 53(14), 54(14), 55(15), 56(14), 57(14), 58(15), 59(15), 60(14),
61(15), 62(15), 63(14), 64(15), 65(15), 66(15), 67(15), 68(15), 69(15), 70(15),
71(15), 72(15), 73(15), 74(15), 75(15), 76(15), 77(15), 78(15), 79(15), 80(15),
81(15), 82(15), 83(15), 84(15), 85(15), 86(15), 87(15), 88(15), 89(15), 90(15),
91(15), 92(15), 93(15), 94(15), 95(15), 96(15), 97(15), 98(16), 99(15), 100(15),
縮まった。
単に掛け算相当をループしただけ。
126(15) の場合だと
inc x1
inc x1
inc x2
inc x2
jz x0,7
dec x0
jz x3,2
inc x0
inc x0
jz x2,12
dec x2
jz x3,7
jz x1,15
dec x1
jz x3,1
間違えました
inc x1
inc x1
inc x2
inc x2
jz x0,7
dec x0
jz x3,2
inc x0
inc x0
jz x2,12
dec x2
jz x3,7
jz x1,15
dec x1
jz x3,2
7: 8
8: 10
9: 12
10: 16
11: 20
12: 25
13: 30
14: 63
15: 126
16: 510
17: 2331
18: 13995
19: 88572
20: 2^2^2^3-4
21: 2^2^2^2^3-4
22: 2^2^2^2^2^3-4
23: 2^2^2^2^2^2^3-4
24: 2^2^2^2^2^2^2^3-4
25: 2^2^2^2^2^2^2^2^3-4
26: > 2^^255
27: > 2^^2^^255
28: > 2^^2^^2^^255
29: > 2^^2^^2^^2^^255
20以降の方法が分からなくなってしまった。
結果のメモが残ってるだけ。
もしかしたら間違っていたかも。
今作れるのは以下まで。
こっちの方が値はきれい。
20: 2^61 -4
21: 2^^5 -4
22: 2^^6 -4
23: 2^^7 -4
24: 2^^8 -4
25: 2^^9 -4
26: 2^^11 -4
27: 2^^(2^^5 *2 -3) -4 > 2^^2^^5 > 2^^^4
28: 2^^^5 -4
29: 2^^^6 -4
inc x3 (n個)
@1:
inc x2
jz x0,@2
dec x0
jz x4,@1
@2:
inc x1
jz x0,@3
dec x0
jz x4,@2
@3:
inc x0
inc x0
jz x1,@4
dec x1
jz x4,@3
@4:
jz x2,@5
dec x2
jz x4,@2
@5:
jz x3,@6
dec x3
jz x4,@1
@6:
28～29 はループを1個多くしただけ
その後は、
アッカーマン関数のループが来て、（ここでグラハム数を超える）
3変数アッカーマン、4変数アッカーマン....と続くと思われる
3=√9
>>32が優勝
猫
猫
どうして足のつま先になるんですか？
ふと。
>>32 に挑戦するか、
...........
いんでぃ
エンジニアと参加願います公安はサリンオウム信者の子供を40歳まで社会から隔離している
オウム信者が地方で現在も潜伏している
それは新興宗教を配下としている公安の仕事だ
発案で盗聴器を開発したら霊魂が寄って呼ぶ来た
<電波憑依>
スピリチャル全否定なら江原三輪氏、高橋佳子大川隆法氏は、幻聴で強制入院矛盾する日本宗教と精神科
<コードレス盗聴>
2004既に国民20%被害250～700台数中国工作員3～7000万円2005ソウルコピー2010ソウルイン医者アカギ絡む<盗聴証拠>
今年５月に日本の警視庁防課は被害者SDカード15分を保持した有る国民に出せ!!<創価幹部>
キタオカ1962年東北生は二十代で2人の女性を害して入信した創価本尊はこれだけで潰せる<<<韓国工作員鸛<<<創価公明党 <テロ装置>>東芝部品)>><宗教<<<公安<<魂複<<官憲>日本終Googl検索
誰か(アメリカ)気づいた
ソウルコピー機器
無差別で猥褻、日本は危険知ったかブッタの日本人
失敗作
テロ資料を忘れずに