プログラムは、連結と分岐で書けるが、P''の焼き直しであるBrainfuckは分岐をループで解決している。
P''もbrainfuckもプログラムアドレス、ラベル、分岐がなく、制御コントロールはネストをできるループしかない。構造化定理により、プログラムは連結、選択、反復で書けるが、P''は連結と反復のみで書けることを示した。
分岐を反複で解決したら、プログラムが複雑になりますが。
チューリング完全性と、プログラムが連結と分岐で書けることとは違いますが演算が出来、メモリアクセスが出来、連結、分岐が書けたらチューリング完全です。
「チューリング完全とは、ある計算モデルAが、理論上、計算可能な全ての計算を実行できることを意味します。言い換えると、どんな複雑な計算でも、十分な時間とメモリさえあれば、Aで表現できるということです。」(Gemini)ちょっと訂正by me.
Computer Scientistさん、教えてくれてありがとうございます。
人間はBrainfuckの全ての計算ができるので、チューリング完全です。
また、brainfuckで、if (*ptr) then A else Bの処理をするコードは以下のようになります。
>+<[>-<A[-]]>[B[-]]<
このコードは、実行前、*(ptr+1)が0である必要があり、実行後、*ptrの値が0になります。ptrは保存されます。メモリセルの値の保存が難しいので等価コードという訳には行きませんが、こんなものでしょう。条件での実行はこうなりますが、条件ジャンプではありません。
brainfuckを更にリダクションするアイディア。 brainfuck extra
扱えるデータが1バイトなので、256ループで255の次は0なので、-は要らない。
これで命令が7種類になる。
brainfuck extraがチューリング完全の限界です。時間が無限に与えられていて、メモリがアドレス0から始まっていて、終わりがないのならば、mem[n]を、mem[f(n)] (f(n)=n//2+1 if n=odd, f(n)=-n//2 if n=even)という様にマッピングすれば、両端に終わりがないテープができるので、メモリがアドレス0から始まっていても、mem[-∞]から、mem[∞]が確保できます。（ヒルベルトの無限のホテルのアイディア）
チューリングマシンが有限時間で停止するかどうかというのが、チューリングマシンの停止問題です。
実装 'bfe' brainfuck extra
メモリとloopstackとprogとlspとidxとlenが有限ですが、勘弁してください。実際のところ、この程度でしょう。
#include <stdio.h>
#include <stdlib.h>
void main(int argc,char *argv[]) {
FILE *fp;
char prog[65536]={0},array[30000]={0},*ptr=array;
int loopstack[1000],lsp=0,idx,len;
fp=fopen(argv[1],"rt");
for(len=0; (prog[len]=fgetc(fp))!=EOF;len++);
fclose(fp);
for(idx=0;idx<len;)
switch (prog[idx++]) {
case '>': ptr++; continue;
case '<': ptr--; continue;
case '+': (*ptr)++; continue;
case '.': putchar(*ptr); continue;
case ',': *ptr=getchar(); continue;
case '[':
if (*ptr) loopstack[lsp++]=idx-1;
else for(int nest=1;idx<len;) {
int c=prog[idx++];
if (c=='[') nest++;
else if (c==']' && --nest==0) break;
}
continue;
case ']': idx=loopstack[--lsp]; continue;
default: continue;
}
}
bfeのアイディアはUrban Müllerさんも考えてたらしいです。
hello world on bfe
++++++++++
[
>+++++++>++++++++++>+++>+<<<<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+.>.
(あまりに露骨なのもあれなので伏字にして)brainf*ck reduction 'bfr'
メモリが有限とすれば、ポインタがメモリアドレス上限まで行ったら0になるようにして、<はいらない。
ポインタがオーバーフローしたら0になる（メモリが有限）というのでは、（仮想的に）チューリング完全にはなりません。bfrはチューリング不完全です。
'bfr' の実装
#include <stdio.h>
#include <stdlib.h>
#define MEMSIZE (30000)
void main(int argc,char *argv[]) {
FILE *fp;
char prog[6553600]={0},array[MEMSIZE]={0},*ptr=array;
int loopstack[1000],lsp=0,idx,len;
fp=fopen(argv[1],"rt");
for(len=0; (prog[len]=fgetc(fp))!=EOF;len++);
fclose(fp);
for(idx=0;idx<len;)
switch (prog[idx++]) {
case '>': ptr++;
if (ptr==&array[MEMSIZE]) ptr=array;
continue;
case '+': (*ptr)++; continue;
case '.': putchar(*ptr); continue;
case ',': *ptr=getchar(); continue;
case '[':
if (*ptr) loopstack[lsp++]=idx-1;
else for(int nest=1;idx<len;) {
int c=prog[idx++];
if (c=='[') nest++;
else if (c==']' && --nest==0) break;
}
continue;
case ']': idx=loopstack[--lsp]; continue;
default: continue;
}
}
bfrによるhello world (最適化なし)
bfrは全く実用にならないなあ。
命令6つが最小かな？ストアされたデータを出力するだけなら、入力,はいらない。5つが最小。
>ポインタを右へ
+ポインタの示すセルをインクリメント
.1バイト出力
[ポインタの示すセルの値が0ならば対応する]の次へジャンプ
]対応する[にジャンプ
.
実装 brainfuck reduction reduction 'bfrr'
#include <stdio.h>
#include <stdlib.h>
#define MEMSIZE (30000)
void main(int argc,char *argv[]) {
FILE *fp;
char prog[6553600]={0},array[MEMSIZE]={0},*ptr=array;
int loopstack[1000],lsp=0,idx,len;
fp=fopen(argv[1],"rt");
for(len=0; (prog[len]=fgetc(fp))!=EOF;len++);
fclose(fp);
for(idx=0;idx<len;)
switch (prog[idx++]) {
case '>': ptr++;
if (ptr==&array[MEMSIZE]) ptr=array;
continue;
case '+': (*ptr)++; continue;
case '.': putchar(*ptr); continue;
case '[':
if (*ptr) loopstack[lsp++]=idx-1;
else for(int nest=1;idx<len;) {
int c=prog[idx++];
if (c=='[') nest++;
else if (c==']' && --nest==0) break;
}
continue;
case ']': idx=loopstack[--lsp]; continue;
default: continue;
}
}
bfrrで、hello.bfrが動きます。
bfr,bfrrはポインタがオーバーフローしたとき0に戻るbrainfuck処理系のサブセットです。
この程度ならUrban Müllerさんも考えてたでしょうね。
入力がなかったら、プログラムを書き換えない限り、全部定数なので、
処理が有限なら、[,]はいらない。以下の命令で良い。
+ポインタの示すセルの値をインクリメント
>ポインタを一つ右へ動かす
.1バイト出力
3つで済む。実装。'bfrf' brainfuck reduction finite.
#include <stdio.h>
#include <stdlib.h>
#define MEMSIZE (30000)
void main(int argc,char *argv[]) {
FILE *fp;
char prog[6553600]={0},array[MEMSIZE]={0},*ptr=array;
int loopstack[1000],lsp=0,idx,len;
fp=fopen(argv[1],"rt");
for(len=0; (prog[len]=fgetc(fp))!=EOF;len++);
fclose(fp);
for(idx=0;idx<len;)
switch (prog[idx++]) {
case '>': ptr++;
if (ptr==&array[MEMSIZE]) ptr=array;
continue;
case '+': (*ptr)++; continue;
case '.': putchar(*ptr); continue;
default: continue;
}
}
これは役に立たない。ちょっとやりすぎた・・・。かな？
bfrfによるhello world.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++..+++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
任意の文字列を表示するだけなら、命令2つで済む。
brainfuckでのhanoi.bfも、文字列定数を表示しているだけです。
+変数Aをインクリメント
.1バイト出力
実装。 これをbrainfuck reduction finite reduced 'bfrfr'と名付ける。
#include <stdio.h>
#include <stdlib.h>
#define MEMSIZE (30000)
void main(int argc,char *argv[]) {
FILE *fp;
char prog[6553600]={0},a=0;
int idx,len;
fp=fopen(argv[1],"rt");
for(len=0; (prog[len]=fgetc(fp))!=EOF;len++);
fclose(fp);
for(idx=0;idx<len;)
switch (prog[idx++]) {
case '+': a++; continue;
case '.': putchar(a); continue;
}
}
bfrfrで、hello.bfrfが動きます。
やりすぎや！ bfrfr,僕ふらふら。