[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 --- 以上
最新の画像[もっと見る]
- あけましておめでとうございます 11年前
- 今年もよろしくお願いいたします 12年前
- あけましておめでとうございます 13年前
- あけましておめでとうございます 16年前