チューリングマシン

10月 3, 2015 admin44 No Comments

無限長のテープに移動して読み書きできるヘッド、そして記憶するメモリだけからなる仮想マシンのことで、これだけの仕組みであらゆる計算をすることができます。チューリングマシンの仕組みをもつプログラム言語で、Brainf*ckというものを取り上げてみました。教育用言語としたときに、ちょっとふさわしくないかもしれない名前ですが、奥の深い言語です。

参考 : http://vipprog.net/wiki/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E8%A8%80%E8%AA%9E/Brainfuck.html

Cトランスレータ : http://esoteric.sange.fi/brainfuck/impl/compilers/BF2C.c
ラズパイ2でコンパイル、実行

これまでの記事とはうって変って、コンソール画面による地味なプログラムですが、チューリングマシンでいうテープとヘッドで読み書きすることをイメージしながら動作を考えていると、プログラミングというより、頭脳ゲームをしている感覚になります。

コンパイル方法

cc -o bf BF2C.c
./bf io1.b > io1.c ; cc -o io1 io1.c

以下ソースと実行画面です。

io1.bは標準入力された文字コードを一つインクリメントして表示するだけのプログラムです。
io2.bは、繰り返しを使って16インクリメントしたものです。
io3.bは、参考ページにあったif構文を実現するものです。説明が省略されていた方を使って実装してみました。@以外を入力すると、一つインクリメントされ、@の場合は3つ表示します。
if構文で、処理が分けられていることを確認できます。表示のためにまた文字コードを戻しているところが効率的ではありませんが、参考サイトの流れからこのようにしました。

io2.bをトランスレートしたものか以下になります。(インデントを整形しました)

#include<stdio.h>
int main() {
    int x[32768];
    int xc;
    for(xc = 0; xc < 32768; xc++) x[xc] = 0;
    xc=0;
    x[xc] = getchar();
    xc++;
    x[xc]++;
    x[xc]++;
    x[xc]++;
    x[xc]++;
    while(x[xc] != 0) {
        x[xc]--;
        xc--;
        x[xc]++;
        x[xc]++;
        x[xc]++;
        x[xc]++;
        xc++;
    }
    xc--;
    putchar(x[xc]);
    printf("\n");
}

#include<stdio.h>

int main() {

int x[32768];

int xc;

for(xc = 0; xc < 32768; xc++) x[xc] = 0;

xc=0;

x[xc] = getchar();

xc++;

x[xc]++;

while(x[xc] != 0) {

x[xc]--;

xc--;

x[xc]++;

xc++;

}

xc--;

putchar(x[xc]);

printf("\n");

}

io3.bの解説です。

なかなか説明が難しいのですが、一つ一つヘッダの位置とメモリの内容を確認しながら、実際に作ってみることが理解の早道のように感じました。

これが何の役に立つのかと思いがちですが、アセンブラ言語でプログラムを組むときには、このような感覚が役に立つと思います。

Category: 未分類

Tags: Brainf*ck