brainfuckの計算機基礎理論

プログラムは、連結と分岐で書けるが、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が有限ですが、勘弁してください。実際のところ、この程度でしょう。

```bfe.c
#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

```hello.bfe
++++++++++
[
	>+++++++>++++++++++>+++>+<<<<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+.>.

```
#### (あまりに露骨なのもあれなので伏字にして)brainf*ck reduction 'bfr'

メモリが有限とすれば、ポインタがメモリアドレス上限まで行ったら0になるようにして、`<`はいらない。
ポインタがオーバーフローしたら0になる（メモリが有限）というのでは、（仮想的に）チューリング完全にはなりません。bfrはチューリング不完全です。

#### 'bfr' の実装

```bfr.c
#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 (最適化なし)

https://github.com/fygar256/brainfuck_interpreter_and_compiler/blob/main/hello.bfr

bfrは全く実用にならないなあ。
命令6つが最小かな？ストアされたデータを出力するだけなら、入力`,`はいらない。5つが最小。

```
>ポインタを右へ
+ポインタの示すセルをインクリメント
.1バイト出力
[ポインタの示すセルの値が0ならば対応する]の次へジャンプ
]対応する[にジャンプ
```
.
実装 brainfuck reduction reduction 'bfrr'

```bfrr.c
#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.

```bfrf.c
#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.

```hello.bfrf
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++..+++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
```

任意の文字列を表示するだけなら、命令2つで済む。
brainfuckでのhanoi.bfも、文字列定数を表示しているだけです。

```
+変数Aをインクリメント
.1バイト出力
```

実装。　これをbrainfuck reduction finite reduced 'bfrfr'と名付ける。

```bfrfr.c
#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,僕ふらふら。