[C][アルゴリズム] チューリングマシンのエミュレーター

[C][アルゴリズム] チューリングマシンのエミュレーター
================================================================================

2ヶ月くらい前にチューリングマシンのエミュレーターを作った。
まだ、公開するつもりではなかった（もう少し検証する予定だった）が、本日が、チュー
リングの生誕100年だったので、ベータ版として公開。
そのうち、直すかもしれない。


■チューリングマシン

チューリングマシンは、テープ、ヘッド、制御部の 3 つから構成されています。

テープは無限の長さを持っていて、各ます目には 0 か 1 のどちらかの記号が書けるよう
になっています。ヘッドはテープ上の記号を読み書きするもので、常にひとつのます目を
見ています。また、制御部は、現在の状態を表す変数と動作を決める規則（プログラム）
が入っています。 制御部は、あらかじめ決められた p0 から pn までの有限個の状態の
うちのひとつを取ります（p0 を初期状態、pn を停止状態といいます）。また、このチ
ューリングマシンは、動作を決めた規則の中で、ヘッドの読んだ記号と現在の状態の 2 
つから次の動作を繰り返します。

●チューリングマシンの動作
① テープに 0 か 1 の記号を書き込む。
② ヘッドを右か左のどちらかに移動する。
③ 制御部の状態を別の（または同じ）状態に移す。

●チューリングマシンを使った計算手順
① テープ上に、入力データに相当する 0，1 の記号列を用意する。
② 制御部の状態を初期状態にして、規則に従い動作を開始する。
③ 制御部の状態が停止状態になったとき、計算を終了したものとする。
 出力（計算結果）は、停止したときのテープ上に残された記号で表される。
③’制御部の状態が停止状態にならないとき、計算は終了しないものとする。

●例
5 ＋ 3 ＝ 8 を行う

テープ上のデータについては、簡単にするために記号 1 の個数で整数値を表します。特
にここでは、n + 1 個の記号 1 で整数の n を表すことにし、足される 2 数の区切りと
してはひとつの記号 0 を使うものとします。

                        5      3
 入力データ：……000001111110111100000……

 このテープ上のデータに対して、次の 4 つの状態と規則でチューリングマシンを動作さ
せると出力はどうなるでしょうか。
（状態と規則）
① 制御部の状態：p0，p1，p2，p3 の 4 つ
         p0 が初期状態、p3 が停止状態

② 規則

状態 入力記号 書込み記号 ヘッドの移動 次の状態
p0     0          0          右         p0
p0     1          0          右         p1
p1     0          0          右         p3
p1     1          0          右         p2
p2     0          1          右         p3
p2     1          1          右         p2

参考）コンピュータシステムの基礎、アイテック情報技術教育研究所 (著) より


■ 実装

上記の説明に合わせて、つぎのように作る。

ルールとテープを標準入力またはファイルから指定して、動かす。
テープの動きの結果は標準出力に出る。

注）ルールはファイルを使わなければならない。

コマンド形式
---
    turing ルール・ファイル名 [テープ・ファイル名]
---


□ テープ

0 と 1 を記述したファイル。


□ ルール

つぎの 5 つをタブ区切りのファイルとして作る。
なお、停止状態は、「次の状態」の中での最大値とする。
---
状態 入力記号 書込み記号 ヘッドの移動 次の状態
---

状態            現在の状態。0 以上の整数で指定。

入力記号        現在の状態で、ヘッドが指す記号。0 または 1

書込み記号        現在の状態で、ヘッドの位置に書き込む記号。0 または 1

ヘッドの移動    ヘッドの移動方向。左は -1、右は 1

次の状態        遷移後の状態。0 以上の整数で指定。最大値が停止状態になる


■ プログラム

□ turing.c
---
/*
 ============================================================================
 Name        : turing.c
 Author      : marunomaruno
 Version     : 0.1, 2012-06-23
 Description : チューリングマシン
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/**
 * ルール
 */
typedef struct {
    int status; // 状態(0以上の値)
    char inSymbol; // 入力記号('0', '1' または 'B')
    char outSymbol; // 書込み記号('0' または '1')
    int direction; // ヘッドの移動方向(-1: 左、1: 右)
    int nextStatus; // 次の状態(0以上の値)
} Rule;

Rule* findRule(char symbol, int status, Rule* ruleTable, int size);
void printlnRule(Rule* rule);
void printRule(Rule* rule);
int findCharOnTape(char* tape, int start, char c);
void printProgress(char* tape, int head, Rule* rule);
void printlnProgress(char* tape, int head, Rule* rule);
void printCount(char* tape);
void printlnCount(char* tape);
int readTape(FILE* in, char* tape);
int readRule(FILE* in, Rule** rule);
void printRuleTable(Rule* rule, int size);
int getStopStatus(Rule* rule, int size);

/**
 * ルールとテープをファイルから入力して、チューリングマシンを実行する。
 * ルールは、次の5項目をタブ区切りで記述する。
 *     状態, 入力記号, 書込み記号, ヘッドの移動, 次の状態
 *
 * @param argc コマンドライン・パラメーター数
 * @param argv コマンドライン・パラメーター値
 *             argv[1]: ルールのファイル。省略時は標準入力
 *             argv[2]: テープのファイル。省略時は標準入力
 * @return 常に0
 */
int main(int argc, char* argv[]) {
    printf("program start¥n");

    const int START_STATUS = 0; // 初期状態

    // 状態, 入力記号, 書込み記号, ヘッドの移動, 次の状態
    Rule* ruleTable;

    int status; // 状態

    char tape[BUFSIZ]; // テープ
    int head; // テープのヘッドの位置

    // ファイル
    FILE* tapeFp;
    FILE* ruleFp;

    switch(argc) {
    case 1:
        ruleFp = stdin;
        tapeFp = stdin;
        break;

    case 2:
        ruleFp = fopen(argv[1], "r");
        tapeFp = stdin;
        break;

    default:
        ruleFp = fopen(argv[1], "r");
        tapeFp = fopen(argv[2], "r");
        break;
    }

    if (ruleFp == NULL) {
        assert(0);
    }
    if (tapeFp == NULL) {
        assert(0);
    }

    // ルールの読み取り
    int ruleSize = readRule(ruleFp, &ruleTable);
    printf("ruleSize = %d¥n", ruleSize);
    printRuleTable(ruleTable, ruleSize);
    fclose(ruleFp);

    // テープの読み取り
    int tapeLength = readTape(tapeFp, tape);;
    printf("tape = ¥"%s¥"¥n", tape);
    fclose(tapeFp);

    // 状態を定義する
    status = START_STATUS; // 初期状態
    int stopStatus = getStopStatus(ruleTable, ruleSize);    // 停止状態

    head = 0;    // テープ・ヘッドの初期化
    while (status != stopStatus) {
        assert(0 <= head && head < tapeLength);
        Rule* rule = findRule(tape[head], status, ruleTable, ruleSize); 
                                                             // ルールを見つける
        printlnProgress(tape, head, rule);
        tape[head] = rule->outSymbol;    // テープの書き換え
        head += rule->direction;    // ヘッドを移動
        status = rule->nextStatus;    // 状態を新しい状態にする
    }
    printlnProgress(tape, head, NULL);

    free(ruleTable);

    printf("program end¥n");
    return EXIT_SUCCESS;
}

/**
 * テープを読み込む。
 * テープの最大長は、BUFSIZ (512) バイトとする。
 * @param in ファイルポインター
 * @param tape テープ
 * @return テープの長さ
 */
int readTape(FILE* in, char* tape) {
    assert(in != NULL);
    assert(tape != NULL);

    fgets(tape, BUFSIZ, in);
    tape[BUFSIZ] = '¥0';
    char* p = strstr(tape, "¥n");
    if (p != NULL) {
        *p = '¥0';
    }
    return strlen(tape);
}

/**
 * ルールを読み込む。
 * なお、ルール配列はこの関数中で領域確保するので、使用側で解放する必要がある。
 * @param in ファイルポインター
 * @param rule ルール配列
 * @return ルール配列のサイズ
 */
int readRule(FILE* in, Rule** rule) {
    assert(in != NULL);
    assert(rule != NULL);

    const int RULE_MALLOC_UNIT = 16;   // ルール配列をとる場合のサイズの初期単位
    const char* DELIMITTER = "¥t";
    int limit = RULE_MALLOC_UNIT;
    int size = 0;
    char buf[BUFSIZ];
    char token[BUFSIZ];

    Rule* p = (Rule*) malloc(RULE_MALLOC_UNIT * sizeof(Rule));
    assert(p != NULL);
    *rule = p;

    size = 0;
    while (fgets(buf, BUFSIZ, in) != NULL) {
        size++;
        if (size == limit) {
            limit *= 2;
            realloc(*rule, limit * sizeof(Rule));
            assert(*rule != NULL);
            p = *rule + size - 1;
        }

        strncpy(token, strtok(buf, DELIMITTER), BUFSIZ);
        token[BUFSIZ] = '¥0';
        p->status = atoi(token);

        strncpy(token, strtok(NULL, DELIMITTER), BUFSIZ);
        token[BUFSIZ] = '¥0';
        p->inSymbol = token[0];

        strncpy(token, strtok(NULL, DELIMITTER), BUFSIZ);
        token[BUFSIZ] = '¥0';
        p->outSymbol = token[0];

        strncpy(token, strtok(NULL, DELIMITTER), BUFSIZ);
        token[BUFSIZ] = '¥0';
        p->direction = atoi(token);

        strncpy(token, strtok(NULL, DELIMITTER), BUFSIZ);
        token[BUFSIZ] = '¥0';
        p->nextStatus = atoi(token);

        p++;
    }

    return size;
}

/**
 * 途中経過をプリントする。
 * @param tape テープ
 * @param head ヘッドの位置
 * @param rule ルール
 */
void printProgress(char* tape, int head, Rule* rule) {
    assert(tape != NULL);
    assert(0 <= head && head < BUFSIZ);

    int i;

    printf("%s ", tape);
    printRule(rule);
    printf(" ");

    printlnCount(tape);

    for (i = 0; i < head; i++) {
        printf(" ");
    }
    printf("^");
    fflush(stdout);
}

/**
 * 途中経過をプリントし、改行する。
 * @param tape テープ
 * @param head ヘッドの位置
 * @param rule ルール
 */
void printlnProgress(char* tape, int head, Rule* rule) {
    assert(tape != NULL);
    assert(0 <= head && head < BUFSIZ);

    printProgress(tape, head, rule);
    printf("¥n");
    fflush(stdout);
}

/**
 * 停止状態を取得する。
 * 停止状態は、ルール中の状態の最大値になる。
 * @param rule ルール
 * @param size ルール配列のサイズ
 * @return 停止状態
 */
int getStopStatus(Rule* rule, int size) {
    assert(rule != NULL);
    assert(size > 0);

    int max = rule->nextStatus;
    rule++;
    int i = 0;
    for (i = 1; i < size; i++) {
        if (max < rule->nextStatus) {
            max = rule->nextStatus;
        }
        rule++;
    }
    return max;
}

/**
 * ルールをプリントする。
 * @param rule ルール
 * @param size ルール配列のサイズ
 */
void printRuleTable(Rule* rule, int size) {
    assert(rule != NULL);
    assert(size > 0);

    int i = 0;
    for (i = 0; i < size; i++) {
        printlnRule(rule);
        rule++;
    }
    fflush(stdout);
}

/**
 * ルールをプリントする。
 * @param rule ルール. NULLのときは、空白をプリントする。
 */
void printRule(Rule* rule) {
    if (rule != NULL) {
        printf("[%d, %c, %c, %d, %d]", rule->status, rule->inSymbol,
                rule->outSymbol, rule->direction, rule->nextStatus);
    } else {
        printf("[      -      ]");
    }

    fflush(stdout);
}

/**
 * ルールをプリントし、改行する。
 * @param rule ルール
 */
void printlnRule(Rule* rule) {
    printRule(rule);
    printf("¥n");
    fflush(stdout);
}

/**
 * 記号と状態から合致するルールを見つける
 * @param symbol 記号
 * @param status 状態
 * @param ruleTable ルール表
 * @param size ruleTableの要素数
 * @return 合致したルール
 */
Rule* findRule(char symbol, int status, Rule* ruleTable, int size) {
    assert(symbol == '0' || symbol == '1');
    assert(status >= 0);
    assert(ruleTable != NULL);
    assert(size > 0);

//    printf("* %c %d %d¥n", symbol, status, size); fflush(stdout);

    Rule* rule = NULL;
    for (rule = ruleTable; rule < ruleTable + size; rule++) {
        assert(ruleTable <= rule && rule < ruleTable + size);
        if (symbol == rule->inSymbol && status == rule->status) {
            return rule;
        }
    }

    assert(0);    // 必ず見つかるはず
    return NULL;
}

/**
 * startの位置から、指定された文字cを見つけ、その位置を返す。
 * @param tape テープ
 * @param start 見つけるための開始位置
 * @param c 見つける文字
 * @return 見つかった位置。見つからない場合は-1
 */
int findCharOnTape(char* tape, int start, char c) {
    assert(tape != NULL);
    assert(start >= 0);
    assert(c == '0' || c == '1');

    int i = -1;

    for (i = start; i < strlen(tape); i++) {
        assert(start <= i && i < strlen(tape));
        if (tape[i] == c) {
            return i;
        }
    }

    return -1;
}

/**
 * テープにある連続した1の数をプリントする。
 * @param tape テープ
 */
void printCount(char* tape) {
    assert(tape != NULL);

    int i = -1;
    int start = -1;

    // 1の位置を検索する
    while ((i = findCharOnTape(tape, (i + 1), '1')) != -1) {
        // 次の0の位置
        start = i;
        if ((i = findCharOnTape(tape, (start + 1), '0')) == -1) {
            printf("%d ", (strlen(tape) - start - 1));
            break;
        }

        printf("%d ", (i - start - 1));
    }
    fflush(stdout);
}

/**
 * テープにある連続した1の数をプリントし、改行する。
 * @param tape テープ
 */
void printlnCount(char* tape) {
    assert(tape != NULL);

    printCount(tape);
    printf("¥n");
    fflush(stdout);
}
---


■ 実行


例にあるように、「5 + 3 = 8」を計算する。


□ tape.txt
---
000001111110111100000
---

1 の並んでいる数(から 1 引いたもの)が数値をあらわす。
間の 0 が区切り。


□ rule.txt
---
0    0    0    1    0
0    1    0    1    1
1    0    0    1    3
1    1    0    1    2
2    0    1    1    3
2    1    1    1    2
---

最大の状態が「3」。


□ 実行結果
---
program start
ruleSize = 6
[0, 0, 0, 1, 0]
[0, 1, 0, 1, 1]
[1, 0, 0, 1, 3]
[1, 1, 0, 1, 2]
[2, 0, 1, 1, 3]
[2, 1, 1, 1, 2]
tape = "000001111110111100000"
000001111110111100000 [0, 0, 0, 1, 0] 5 3 
^
000001111110111100000 [0, 0, 0, 1, 0] 5 3 
 ^
000001111110111100000 [0, 0, 0, 1, 0] 5 3 
  ^
000001111110111100000 [0, 0, 0, 1, 0] 5 3 
   ^
000001111110111100000 [0, 0, 0, 1, 0] 5 3 
    ^
000001111110111100000 [0, 1, 0, 1, 1] 5 3 
     ^
000000111110111100000 [1, 1, 0, 1, 2] 4 3 
      ^
000000011110111100000 [2, 1, 1, 1, 2] 3 3 
       ^
000000011110111100000 [2, 1, 1, 1, 2] 3 3 
        ^
000000011110111100000 [2, 1, 1, 1, 2] 3 3 
         ^
000000011110111100000 [2, 1, 1, 1, 2] 3 3 
          ^
000000011110111100000 [2, 0, 1, 1, 3] 3 3 
           ^
000000011111111100000 [      -      ] 8 
            ^
program end
---

                                                                            以上