summaryrefslogtreecommitdiff
path: root/tm.c
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2007-11-22 23:54:59 +0000
committerDimitri Sokolyuk <demon@dim13.org>2007-11-22 23:54:59 +0000
commitb550319f4cf2d37b3133aff724fa7cc3057e5bc6 (patch)
treefa5c49550deea268374ed2ad6789fab1aeb0a41f /tm.c
Turing Machine
Diffstat (limited to 'tm.c')
-rw-r--r--tm.c353
1 files changed, 353 insertions, 0 deletions
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 <demon@vhost.dyndns.org>
+ *
+ * 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 <assert.h>
+#include <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+
+/* 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);
+}