summaryrefslogtreecommitdiff
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
Turing Machine
-rw-r--r--Makefile4
-rw-r--r--progs/add.tm25
-rw-r--r--progs/add00.tm40
-rw-r--r--progs/bb-brady.tm8
-rw-r--r--progs/bb-lin-rado-2.tm8
-rw-r--r--progs/bb-lin-rado.tm8
-rw-r--r--progs/bb-rado.tm6
-rw-r--r--progs/bb6.tm14
-rw-r--r--progs/bbeaver.tm30
-rw-r--r--progs/bbeaver2.tm7
-rw-r--r--progs/beaver.tm7
-rw-r--r--progs/beaver2.tm11
-rw-r--r--progs/beaver_1.tm7
-rw-r--r--progs/bincounter.tm11
-rw-r--r--progs/clean.tm12
-rw-r--r--progs/copy.tm12
-rw-r--r--progs/count.tm12
-rw-r--r--progs/deccounter.tm28
-rw-r--r--progs/first.tm5
-rw-r--r--progs/hexcounter.tm40
-rw-r--r--progs/inverse.tm5
-rw-r--r--progs/move.tm7
-rw-r--r--progs/palindrome.tm33
-rw-r--r--tm.c353
24 files changed, 693 insertions, 0 deletions
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 <bsd.prog.mk>
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
+I11>I
+I00>I
+I++<D
+D1W>M
+D0Z>M
+D_Z>M
+M00>M
+M11>M
+MWW>M
+MZZ>M
+M++>M
+M__<N
+N1_<1
+N0_<0
+N+_<C
+100<1
+111<1
+1++<1
+1W0<J
+1Z1<D
+J1Z<Y
+J0W>M
+J_W>M
+011<0
+000<0
+0++<0
+0W1<D
+0Z0<D
+Y10<Y
+Y01>M
+Y_1>M
+C00<C
+C11<C
+CZ0<C
+CW1<C
+C__NH
diff --git a/progs/bb-brady.tm b/progs/bb-brady.tm
new file mode 100644
index 0000000..ad66d18
--- /dev/null
+++ b/progs/bb-brady.tm
@@ -0,0 +1,8 @@
+# Brady (1988) and Michel (2004)
+%A0H
+A01RB
+A12LB
+A21RH
+B02LA
+B12RB
+B21LB
diff --git a/progs/bb-lin-rado-2.tm b/progs/bb-lin-rado-2.tm
new file mode 100644
index 0000000..45a2d25
--- /dev/null
+++ b/progs/bb-lin-rado-2.tm
@@ -0,0 +1,8 @@
+# Lin and Rado (1965)
+%A0H
+A01RB
+A11RH
+B00RC
+B11RB
+C01LC
+C11LA
diff --git a/progs/bb-lin-rado.tm b/progs/bb-lin-rado.tm
new file mode 100644
index 0000000..88f7fc0
--- /dev/null
+++ b/progs/bb-lin-rado.tm
@@ -0,0 +1,8 @@
+# Lin and Rado (1965)
+%A0H
+A01RB
+A11RH
+B01LB
+B10RC
+C01LC
+C11LA
diff --git a/progs/bb-rado.tm b/progs/bb-rado.tm
new file mode 100644
index 0000000..c1481d3
--- /dev/null
+++ b/progs/bb-rado.tm
@@ -0,0 +1,6 @@
+# Rado (1962) Besy Beaver
+%A0H
+A01RB
+A11LB
+B01LA
+B11RH
diff --git a/progs/bb6.tm b/progs/bb6.tm
new file mode 100644
index 0000000..2df5c5c
--- /dev/null
+++ b/progs/bb6.tm
@@ -0,0 +1,14 @@
+# 6-State Busy Beaver
+%1 h
+1 1<2
+111<1
+2 1>3
+211>2
+3 >6
+311>4
+4 1<1
+41 >5
+5 <1
+511>3
+6 1<5
+611<h
diff --git a/progs/bbeaver.tm b/progs/bbeaver.tm
new file mode 100644
index 0000000..60db8ee
--- /dev/null
+++ b/progs/bbeaver.tm
@@ -0,0 +1,30 @@
+# old read new write move
+# +---+--------------------+
+# | A | 0 B 1 R |
+# | | 1 C 1 L |
+# +---+--------------------+
+# | B | 0 A 0 L |
+# | | 1 D 0 L |
+# +---+--------------------+
+# | C | 0 A 1 L |
+# | | 1 H 1 L |
+# +---+--------------------+
+# | D | 0 B 1 L |
+# | | 1 E 1 R |
+# +---+--------------------+
+# | E | 0 D 0 R |
+# | | 1 B 0 R |
+# +---+--------------------+
+
+%a h
+
+a *rb
+a**lc
+b la
+b* ld
+c *la
+c**lh
+d *lb
+d**re
+e rd
+e* rb
diff --git a/progs/bbeaver2.tm b/progs/bbeaver2.tm
new file mode 100644
index 0000000..e82412b
--- /dev/null
+++ b/progs/bbeaver2.tm
@@ -0,0 +1,7 @@
+%A H
+A *RB
+A**LC
+B *LA
+B**RB
+C *LB
+C**NH
diff --git a/progs/beaver.tm b/progs/beaver.tm
new file mode 100644
index 0000000..8b258de
--- /dev/null
+++ b/progs/beaver.tm
@@ -0,0 +1,7 @@
+%A0H
+A01RB
+A11LC
+B01LA
+B11RB
+C01LB
+C11NH
diff --git a/progs/beaver2.tm b/progs/beaver2.tm
new file mode 100644
index 0000000..3a63a23
--- /dev/null
+++ b/progs/beaver2.tm
@@ -0,0 +1,11 @@
+#initia string
+!1
+# init state, blank, halt state
+%A0H
+# state, scan, print, move, state
+A01RB
+A11LC
+B01LA
+B11RB
+C01LB
+C11NH
diff --git a/progs/beaver_1.tm b/progs/beaver_1.tm
new file mode 100644
index 0000000..cdb610d
--- /dev/null
+++ b/progs/beaver_1.tm
@@ -0,0 +1,7 @@
+%A H
+A #>B
+A##<C
+B #<A
+B##>B
+C #<B
+C## H
diff --git a/progs/bincounter.tm b/progs/bincounter.tm
new file mode 100644
index 0000000..7e75b80
--- /dev/null
+++ b/progs/bincounter.tm
@@ -0,0 +1,11 @@
+# binar counter
+# never stops
+
+%a h
+
+a 1rb
+a01rb
+a10la
+b11rb
+b00rb
+b la
diff --git a/progs/clean.tm b/progs/clean.tm
new file mode 100644
index 0000000..6bd6406
--- /dev/null
+++ b/progs/clean.tm
@@ -0,0 +1,12 @@
+!aaaaa aaa
+%0 6
+0a r1
+1aar1
+1 ar2
+2 l3
+3aal3
+3 r0
+2aal4
+4a l5
+5aal5
+5 an6
diff --git a/progs/copy.tm b/progs/copy.tm
new file mode 100644
index 0000000..7438ac4
--- /dev/null
+++ b/progs/copy.tm
@@ -0,0 +1,12 @@
+!aaaa
+%a h
+1 nh
+1a r2
+2 r3
+2aar2
+3 al4
+3aar3
+4 l5
+4aal4
+5 ar1
+5aal5
diff --git a/progs/count.tm b/progs/count.tm
new file mode 100644
index 0000000..3a61acb
--- /dev/null
+++ b/progs/count.tm
@@ -0,0 +1,12 @@
+#http://www.maa.org/editorial/mathgames/mathgames_06_07_04.html
+%a h
+a 1lb
+b 1lc
+c 1ld
+d 1ra
+e 1lh
+a11rc
+b11lb
+c1 re
+d11rd
+e1 ra
diff --git a/progs/deccounter.tm b/progs/deccounter.tm
new file mode 100644
index 0000000..bdb66f9
--- /dev/null
+++ b/progs/deccounter.tm
@@ -0,0 +1,28 @@
+# decimal counter
+# never stops
+
+%a h
+
+a 1rb
+a01rb
+a12rb
+a23rb
+a34rb
+a45rb
+a56rb
+a67rb
+a78rb
+a89rb
+a90la
+
+b00rb
+b11rb
+b22rb
+b33rb
+b44rb
+b55rb
+b66rb
+b77rb
+b88rb
+b99rb
+b la
diff --git a/progs/first.tm b/progs/first.tm
new file mode 100644
index 0000000..ec04da5
--- /dev/null
+++ b/progs/first.tm
@@ -0,0 +1,5 @@
+%b h
+b 0rc
+c re
+e 1rf
+f rb
diff --git a/progs/hexcounter.tm b/progs/hexcounter.tm
new file mode 100644
index 0000000..a8a43ff
--- /dev/null
+++ b/progs/hexcounter.tm
@@ -0,0 +1,40 @@
+# hex counter
+# never stops
+
+%a h
+
+a 1rb
+a01rb
+a12rb
+a23rb
+a34rb
+a45rb
+a56rb
+a67rb
+a78rb
+a89rb
+a9Arb
+aABrb
+aBCrb
+aCDrb
+aDErb
+aEFrb
+aF0la
+
+b00rb
+b11rb
+b22rb
+b33rb
+b44rb
+b55rb
+b66rb
+b77rb
+b88rb
+b99rb
+bAArb
+bBBrb
+bCCrb
+bDDrb
+bEErb
+bFFrb
+b la
diff --git a/progs/inverse.tm b/progs/inverse.tm
new file mode 100644
index 0000000..4233fcd
--- /dev/null
+++ b/progs/inverse.tm
@@ -0,0 +1,5 @@
+!11101101
+%0 1
+010r0
+001r0
+0 n1
diff --git a/progs/move.tm b/progs/move.tm
new file mode 100644
index 0000000..66abb9a
--- /dev/null
+++ b/progs/move.tm
@@ -0,0 +1,7 @@
+!aaaaa
+%a h
+aaara
+a alb
+baalb
+b rc
+ca ra
diff --git a/progs/palindrome.tm b/progs/palindrome.tm
new file mode 100644
index 0000000..55c77dd
--- /dev/null
+++ b/progs/palindrome.tm
@@ -0,0 +1,33 @@
+! BABBBAABBBAB
+%1 H
+1 #>2
+2A >3
+2B >4
+2 <7
+3AA>3
+3BB>3
+3 <5
+4AA>4
+4BB>4
+4 <6
+5A <B
+5B <C
+5 <7
+6A <C
+6B <B
+6 <7
+7 <7
+7# >8
+8 Y>9
+9 E>A
+A S>H
+BAA<B
+BBB<B
+B >2
+CA <C
+CB <C
+C <C
+C# >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 <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);
+}