brainf*ckってのは難解プログラミング言語と呼ばれるジャンルの実用性は無いけど面白いプログラミング言語の1つです。 難解プログラミング言語界の中でもbrainf*ckは最もシンプルで分かりやすい言語です。詳しくはググれ。
というわけで具体的に計算を作ってみました。m,nの部分を任意の個数の+に置換して数を表現して下さい。 ウォーミングアップとしてまずは足し算から。
m>n[<+>-]
とってもシンプルです。nの部分にある値が0になるまでmに1を加えてnから1を引くということを繰り返しています。
次掛け算
m>n[<[>>+>+<<<-]>>>[<<<+>>>-]<<-]
nの隣の位置にmをn回足し続けるコードです。ただ、普通にやると元の位置のnが0になってしまうので隣にも足しておいてそれを元に戻すという方法でnが消えないようになってます。これ変数のコピーとかでも多用するのでbrainf*ckでは必須のテクニックです。多分。
m , n , 0 , 0 0 ,n-1, m , m m ,n-1, m , 0 0 ,n-2,2m , m m ,n-2,2m , 0 (以下繰り返し)
そして累乗
m>n>+<[<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<[>>+<<-]>[>[<<+>>>+<-]>[<+>-]<<-]>[-]<<<-]
ちょっと分かりにくいのでコメント付で
[>+<[ # m ,(n), 1 < #(m), n , 1 [>>>+>+<<<<-]>>>>[<<<<+>>>>-] # m , n , 1 , m ,(0) << # m , n ,(1), m , 0 [>>+<<-] # m , n ,(0), m , 1 >[ # m , n , 0 ,(m), 1 > # m , n , 0 , m ,(1), 0 [<<+>>>+<-]>[<+>-] # m , n , 1 , m , 1 ,(0) <<- # m , n , 1 ,(m-1), 1 , 0 ] # m , n ,1*m,(0), 1 >[-] # m , n ,1*m, 0 ,(0) <<<- # m,(n-1),1*m, 0 , 0 ] # m ,(0),m^n, 0 , 0]
これを発展させてm→n→aを実装するとこうなる。
>>>m>n>a-<<[>>[-<-[<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<-[>>>+<<<-]>[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<]>[-]<<<<->>[<<+>>-]<]+<[<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<[>>+<<-]>[>[<<+>>>+<-]>[<+>-]<<-]>[-]<<<-]>[<<<<+>>>>-]<<[-]<<<]
コメント
>>>m>n>a-<<[ #(m),n,a-1 >>[- # m,n,(a-2) <-[ # m,(n-1),a-2 <[>>>+>+<<<<-]>>>>[<<<<+>>>>-] <<<-[>>>+<<<-] >[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<< #m,0,a-2,m,(n-2),a-2 ] #…,m,0,a-2,m,(0),a-2 >[-]<<[<<+>>-]< #…,m,m,(a-2),0,0,0 ] #…,m',0,a',m,n,(0) +<[<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<[>>+<<-]>[>[<<+>>>+<-]>[<+>-]<<-]>[-]<<<-] #…,m',0,a',m,(0),m^n >[<<<<+>>>>-]<<[-]<<< #…,(m'),m^n,a',0,0,0 ]
brainf*ckは0しか検出出来ないので三番目の引数は本来の表記より1小さくした。後再帰関数をループでやるといつ終わって良いか分からなくなるので初期位置を右にずらした。何?4つ以上の矢印?引数の個数が可変になった場合の実装方法がちょっと思いつかんですね。
さてお待ちかね今回の本丸アッカーマン関数がこちら。
>>m>n<<<->>+[-[>[<[>>+>+<<<-]>>>-[<<<+>>>-]<<-[>>+<<-]>>]+<-]>[<<+>>-]<<+<+]
さっきより短くなって満足である。
<<<->>+[- #-1,0,m,n [ #(m),n >[ #m,(n) <[>>+>+<<<-]>>>-[<<<+>>>-] <<-[>>+<<-]>> #m-1,0,m,(n-1) ] #…,m-1,0,m,(0) +<- #…,m-1,0,(m-1),1 ] #…,m,0,(0),n >[<<+>>-]<<+< #…,(m),n+1,0,0 +]
再帰を終わらせるのが面倒で油断すると永遠に終わらなくなってしまう。何?多変数アッカーマン?引数の個数は固定してくれってさっき言ったじゃろ!
ちなみに計算するだけで出力は作ってないし桁あふれは想定してないしゆるゆるです。文字出力はあっても数値出力は無いので「十進数で出力する」っていうのもこれはこれで挑み甲斐のある問題だと思いますが、面倒くさい本題からずれるのでやりませんでした。
ところでちょっとよく分かってないんですが「n文字以内のbrainf*ck(桁あふれは考慮しない)で表記し得る最大の有限数」と定義される関数は計算不可能関数になるんですかね?
(追記)
インタプリタです。
[[1]]