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/

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

1. Program implementing Post Tag System as applied to a Turing Machine

2. Turing Machine to Tag System Converter

3. how do u invoke Tag b's Tag Handler from within Tag a's tag Handler?

4. 2 dimensional Turing machine can solve Halting problem of a 1 dimensional turing machine

5. 2 dimensional (planar) Turing Machine v/s 1 dimensional Turing Machine

6. how to simulate a Turing Machine on a Post Machine ??

7. Exploiting limitations of Turing machines in Turing tests?

8. Turing was Wrong (was: C++ Simulator of a Universal Turing Machine)

9. Exploiting limitations of Turing machines in Turing tests?

10. Turing machine simulator, "Turing's World"

11. a follow-up to a post of 2001 on a complex-behaviour Turing machine

12. Programming a Turing Machine

13. Turing Machine versus parallel programming

14. 2 Dimensional (planar) Tuning Machine v/s 1 dimensional Turing machine

2 post • Page:**1** of **1**