From b550319f4cf2d37b3133aff724fa7cc3057e5bc6 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Thu, 22 Nov 2007 23:54:59 +0000 Subject: Turing Machine --- Makefile | 4 + progs/add.tm | 25 ++++ progs/add00.tm | 40 ++++++ progs/bb-brady.tm | 8 ++ progs/bb-lin-rado-2.tm | 8 ++ progs/bb-lin-rado.tm | 8 ++ progs/bb-rado.tm | 6 + progs/bb6.tm | 14 ++ progs/bbeaver.tm | 30 +++++ progs/bbeaver2.tm | 7 + progs/beaver.tm | 7 + progs/beaver2.tm | 11 ++ progs/beaver_1.tm | 7 + progs/bincounter.tm | 11 ++ progs/clean.tm | 12 ++ progs/copy.tm | 12 ++ progs/count.tm | 12 ++ progs/deccounter.tm | 28 ++++ progs/first.tm | 5 + progs/hexcounter.tm | 40 ++++++ progs/inverse.tm | 5 + progs/move.tm | 7 + progs/palindrome.tm | 33 +++++ tm.c | 353 +++++++++++++++++++++++++++++++++++++++++++++++++ 24 files changed, 693 insertions(+) create mode 100644 Makefile create mode 100644 progs/add.tm create mode 100644 progs/add00.tm create mode 100644 progs/bb-brady.tm create mode 100644 progs/bb-lin-rado-2.tm create mode 100644 progs/bb-lin-rado.tm create mode 100644 progs/bb-rado.tm create mode 100644 progs/bb6.tm create mode 100644 progs/bbeaver.tm create mode 100644 progs/bbeaver2.tm create mode 100644 progs/beaver.tm create mode 100644 progs/beaver2.tm create mode 100644 progs/beaver_1.tm create mode 100644 progs/bincounter.tm create mode 100644 progs/clean.tm create mode 100644 progs/copy.tm create mode 100644 progs/count.tm create mode 100644 progs/deccounter.tm create mode 100644 progs/first.tm create mode 100644 progs/hexcounter.tm create mode 100644 progs/inverse.tm create mode 100644 progs/move.tm create mode 100644 progs/palindrome.tm create mode 100644 tm.c diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..1fdba70 --- /dev/null +++ b/Makefile @@ -0,0 +1,4 @@ +PROG= tm +NOMAN= + +.include diff --git a/progs/add.tm b/progs/add.tm new file mode 100644 index 0000000..6083247 --- /dev/null +++ b/progs/add.tm @@ -0,0 +1,25 @@ +!1399 +%A H +A00RA +A11RA +A22RA +A33RA +A44RA +A55RA +A66RA +A77RA +A88RA +A99RA +A99RA +A LB +B01NH +B12NH +B23NH +B34NH +B45NH +B56NH +B67NH +B78NH +B89NH +B90LB +B 1NH diff --git a/progs/add00.tm b/progs/add00.tm new file mode 100644 index 0000000..a1153b4 --- /dev/null +++ b/progs/add00.tm @@ -0,0 +1,40 @@ +!10011+10101 +#101000 +%I_H +I__I +I00>I +I++M +D0Z>M +D_Z>M +M00>M +M11>M +MWW>M +MZZ>M +M++>M +M__M +J_W>M +011<0 +000<0 +0++<0 +0W1M +Y_1>M +C003 +211>2 +3 >6 +311>4 +4 1<1 +41 >5 +5 <1 +511>3 +6 1<5 +611B +A##B +C #2 +2A >3 +2B >4 +2 <7 +3AA>3 +3BB>3 +3 <5 +4AA>4 +4BB>4 +4 <6 +5A 8 +8 Y>9 +9 E>A +A S>H +BAA2 +CA D +D N>E +E O>H + diff --git a/tm.c b/tm.c new file mode 100644 index 0000000..694cd48 --- /dev/null +++ b/tm.c @@ -0,0 +1,353 @@ +/* $Id$ */ +/* + * Copyright (c) 2007 Dimitri Sokolyuk + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ +/* TuringMachine */ + +#include +#include +#include +#include +#include +#include + + +/* tape, head, table, state register */ + +struct table { + struct tulpe *tulpe; + int state; + char *init; +}; + +struct tulpe { + char curst; /* current state */ + char ssymb; /* symbol scanned */ + char psymb; /* print symbol/erase E/none N */ + char move; /* move tape left L/none N/right R */ + char newst; /* new state */ + struct tulpe *next; +}; + +struct tape { + struct cell *head; + struct cell *begin; + struct cell *end; +}; + +struct cell { + char symb; + struct cell *left; + struct cell *right; +}; + +/* + * beaver: A01RB A11LC B01LA B11RB C01LB C11NH + */ + +typedef struct tape Tape; +typedef struct cell Cell; +typedef struct table Table; +typedef struct tulpe Tulpe; +char blank = ' '; +char init = 'A'; +char stop = 'H'; +int width = 15; +int counter = 0; +int cells = 0; + +Tape *alloctape(char *); +Cell *alloccell(void); +Table *alloctable(char *); +Tulpe *findtulpe(Table *, Cell *); +int movehead(Tape *, char); +int execute(Tape *, Table *, int); +void printtape(Tape *, Tulpe *, int, char); +void printtable(Table *); +void printtulpe(Tulpe *, char); + +Tape * +alloctape(char *init) +{ + Tape *t; + Cell *c; + char *s; + + t = malloc(sizeof(Tape)); + assert(t); + + c = alloccell(); + t->head = c; + t->begin = c; + t->end = c; + + s = init; + if (init != NULL) { + while (*s != '\0' && *s != '\n') { + t->head->symb = *(s++); + movehead(t, 'R'); + } + while (s-- != init) + movehead(t, 'L'); + } + + return t; +} + +Cell * +alloccell(void) +{ + Cell *c; + + c = malloc(sizeof(Cell)); + assert(c); + + c->left = NULL; + c->right = NULL; + c->symb = blank; + ++cells; + + return c; +} + +Table * +alloctable(char *fname) +{ + Table *tab; + Tulpe *t, **pt; + FILE *fd; + char *buf; + size_t len; + + t = NULL; + pt = &t; + + tab = malloc(sizeof(Table)); + assert(tab); + + tab->init = NULL; + + fd = fopen(fname, "r"); + assert(fd); + while ((buf = fgetln(fd, &len)) != NULL) { + switch (*buf) { + case '#': /* commentar */ + case '\n': /* empty line */ + continue; + case '!': /* initial string */ + tab->init = calloc(len, sizeof(char)); + assert(tab->init); + memcpy(tab->init, ++buf, len); + continue; + case '%': + ++buf; + init = buf[0]; + blank = buf[1]; + stop = buf[2]; + continue; + default: + if (len < 5) + continue; + + *pt = malloc(sizeof(Tulpe)); + assert(*pt); + + (*pt)->curst = buf[0]; + (*pt)->ssymb = buf[1]; + (*pt)->psymb = buf[2]; + (*pt)->move = buf[3]; + (*pt)->newst = buf[4]; + + pt = &(*pt)->next; + } + } + fclose(fd); + + tab->tulpe = t; + tab->state = t->curst; + + return tab; +} + +Tulpe * +findtulpe(Table *tab, Cell *cell) +{ + Tulpe *t; + + for (t = tab->tulpe; t != NULL; t = t->next) { + if (tab->state != t->curst) + continue; + if (cell->symb != t->ssymb) + continue; + return t; + } + + return NULL; +} + +int +movehead(Tape *tape, char move) +{ + Cell *c; + + switch (move) { + case 'L': + case 'l': + case '<': + if (tape->head->left == NULL) { + c = alloccell(); + tape->head->left = c; + c->right = tape->head; + tape->begin = c; + } + tape->head = tape->head->left; + break; + case 'R': + case 'r': + case '>': + if (tape->head->right == NULL) { + c = alloccell(); + tape->head->right = c; + c->left = tape->head; + tape->end = c; + } + tape->head = tape->head->right; + break; + case 'N': + case 'n': + case ' ': + default: + break; + } + + return 0; +} + +int +execute(Tape *tape, Table *tab, int u) +{ + Tulpe *t; + + if (tab->init != NULL) + printtape(tape, NULL, width, '\r'); + + while (tab->state != stop) { + t = findtulpe(tab, tape->head); /* read, find */ + if (t == NULL) { + fprintf(stderr, "\ncannot find proper tulpe"); + exit(1); + } + + tape->head->symb = t->psymb; /* write */ + + printtape(tape, t, width, '\r'); + usleep(u); + + movehead(tape, t->move); /* move head */ + tab->state = t->newst; /* save new state */ + + ++counter; + } + printtape(tape, NULL, width, '\n'); + + return 0; +} + +void +printtape(Tape *t, Tulpe *tulpe, int n, char fin) +{ + int i; + Cell *c; + char *s; + char *ps; + + s = calloc(n + 1 + n, sizeof(char)); + + for (i = 0; i < n + 1 + n; i++) + s[i] = blank; + + + for (i = 0, c = t->head; i < n && c != NULL; i++, c = c->left) + s[n - i] = c->symb; + for (i = 0, c = t->head; i < n && c != NULL; i++, c = c->right) + s[n + i] = c->symb; + s[n] = t->head->symb; + + /* printf("State: %c %c\t", state, move); */ + printtulpe(tulpe, '\t'); + + ps = s; + for (i = 0; i < n; i++) + printf("%c ", *(ps++)); + printf("(%c)", *(ps++)); + for (i = 0; i < n; i++) + printf(" %c", *(ps++)); + + printf("%c", fin); + fflush(stdout); + + free(s); +} + +int +main(int argc, char **argv) +{ + Tape *tape; + Table *table; + int delay = 250000; + + /* TODO: add scroll flag & execution velocity parameter */ + if (argc != 2) + exit(1); + + if (**argv == 'f') + delay /= 100; /* fast */ + + table = alloctable(argv[1]); + tape = alloctape(table->init); + + execute(tape, table, delay); + + printf("halted after %d steps\n", counter); + printf("wasted %d cells\n", cells); + + return 0; +} + +void +printtable(Table *tab) +{ + Tulpe *t; + + for (t = tab->tulpe; t != NULL; t = t->next) { + printtulpe(t, '\n'); + printf("\n"); + } +} + +void +printtulpe(Tulpe *t, char fin) +{ + if (t == NULL) + printf("\t"); + else + printf("%c %c %c %c %c", + t->curst, + t->ssymb, + t->psymb, + t->move, + t->newst); + printf("%c", fin); +} -- cgit v1.2.3