Program implementing Post Tag System as applied to a Turing Machine

Program implementing Post Tag System as applied to a Turing Machine

Post by Alex Vinok » Thu, 09 Sep 2004 00:36:31


Is there any C/C++-program which implements Post Tag System as applied to a Turing Machine?

In other words, let T be some (one-tape) Turing Machine M = <Q, A, I, q0, qfin, b, s> where
* Q = {q0, q1, ..., qk, qfin} is a set of states;
* A = {i1, ..., in, a1, ..., am} is a set of the tape alphabet;
* I = {i1, ..., in} is a set of the input alphabet;
* q0 is the initial state;
* qfin is the halting state;
* b is the blank symbol;
* s : QxA -> QxAx{L, R, S} is the transition table, where L is left shift, R is right shift, S is no shift.

Further, let w be some input word of M.

Is there any C/C++-program which gets as input
* set of states Q,
* tape alphabet A,
* blank symbol b,
* transition table s,
* input word w
and produces as output
* Post Tag System string.


--
Alex Vinokur
http://www.yqcomputer.com/
http://www.yqcomputer.com/
 
 
 

Program implementing Post Tag System as applied to a Turing Machine

Post by eray » Fri, 10 Sep 2004 01:32:38


A TM to Tag System compiler? Interesting idea. If you take it in the
Platonist sense, there is at least one such program since TMs are
equivalent to Post Tag Systems :) You could use the representation in
Minsky's 1961 and *** e and Minsky's 1964 papers I suppose as
mentioned on mathworld:
http://www.yqcomputer.com/

I tried some google queries and found such a program by Andr?Betz :

http://www.yqcomputer.com/

---------------------------------------------------------------------
TM2TS.java converts from Turing Machine Definition with 2 Symbols to
Tag System Definition
---------------------------------------------------------------------

He says that it is described in his book and home page:
http://www.yqcomputer.com/

You can re-implement this code in C++ and make it run faster than the
Java version, I'm sure.

It looks like there is at least one other person who is interested in
the practical implementation of these theoretical devices as much as
yourself. I wonder what are you working on, could you explain briefly?

Regards,

Eray Ozkural