Alex Vinokur - 2003-12-21

C++ Simulator of a Post Machine can be downloaded at :
* http://alexvn.freeservers.com/s1/post-m.html
* http://sourceforge.net/projects/turing-machine/

Source of Post Machine description :
* V.A.Uspensky, "A Post Machine" (in Russian), Moscow, "Nauka", 1979.

The program simulates Deterministic and Nondeterministic Multitape Post Machine (PM).
Detailed log file is generated.

Resources used (input size, output size, PM-space, PM-time) are computed as well.

A simulated Post machine is defined by the set of setup files and data :
* description file (optional),
* number of tapes,
* command file,
* file(s) of input word(s).

Set of simulated Post machines is defined by a metafile.
Each row of the metafile contains data related to some Post machine.

The following demo Post machines are demonstrated with using the C++ Simulator :
1. An addition of one to a number  : Deterministic, 1 tape
2. An addition of two numbers      : Deterministic, 1 tape
3. An addition of two numbers      : Deterministic, 2 tape
4. A recognition of odd numbers    : Deterministic, 1 tape
5. A recognition of odd numbers    : Nondeterminitsic, 1 tape

Log file fragments are shown below

-----------------------
--- File metafile
-----------------------
   Row#  1 ---> add1.dsc 1 add1.cmd add1_1.in add1_2.in add1_3.in
   Row#  2 ---> add2.dsc 1 add2.cmd add2_1.in add2_2.in
   Row#  3 ---> add3.dsc 2 add3.cmd add3_1.in add3_2.in
   Row#  4 ---> recogn.dsc 1 recogn.cmd recogn_1.in recogn_2.in
   Row#  5 ---> recogn.dsc 1 recogn-n.cmd recogn_1.in recogn_2.in
-----------------------

   ========== Data selected from Metafile metafile ==========
     ---------- Nondeterministic Post Machine# 1 ----------
      Description file name   : add1.dsc
      Number of tapes         : 1
      Commands file name      : add1.cmd
      Input words files names : add1_1.in add1_2.in add1_3.in

        %%===========================================
        %%===== Nondeterministic Post Machine# 1 ====
        %%======= Machine Definition : BEGIN ========
        %%===========================================

###### Nondeterministic Post Machine Definition ######
###### This Machine is actually Deterministic!!! #####

    ====== Description ======

An addition of one to a number

Source : V.A.Uspensky, "A Post Machine" (in Russian), Moscow, "Nauka", 1979.

The program adds one to a number.
A number 'n' is represented by (n+1) 1-s.
Sample :
0 is represented as 1
1 is represented as 1 1
3 is represented as 1 1 1 1

Number of tapes used : 1

Input  : A number 'n'
Output : Resulting number 'n+1'

Sample-1
Input  : 1 1 1 1
Output : 1 1 1 1 1

Sample-2
Input  : b b b 1 1 1 1
Output : 1 1 1 1 1

    ====== Command Numeration ======
Initial commands  : 1
Halting commands  : 5
Internal commands : 2 3 4 6

    ====== Alphabet Definition ======
       ------ Tape# 0 ------
Blank symbol : b
Label symbol : 1

    ====== Command Definition ======
Command#   1 :   1 ---> BLANK  6 2
Command#   2 :   2 ---> LEFT   3
Command#   3 :   3 ---> BLANK  4 2
Command#   4 :   4 ---> WRITE  5
Command#   5 :   5 ---> STOP  
Command#   6 :   6 ---> RIGHT  1

        %%===========================================
        %%======= Machine Definition :  END  ========
        %%===== Nondeterministic Post Machine# 1 ====
        %%===========================================

        %%===========================================
        %%===== Nondeterministic Post Machine# 1 ====
        %%========= Processing Input Words  =========
        %%============= Set# 1 : BEGIN ==============
        %%===========================================

##### < Run 1.1 > Input word(s) & head start position(s) on tape(s) #####
Tape#0 : Word = 1 1 1 1 ;  Head pos = 0

##### < Run 1.1 > Processing #####
----- < Run 1.1 > Initial Configuration -----
Tape#0 : [1]  1   1   1 
< Run 1.1 > Applied Command#   1 :   1 ---> BLANK  6 2

----- < Run 1.1 > Configuration#1 -----
Tape#0 : [1]  1   1   1 
< Run 1.1 > Applied Command#   2 :   2 ---> LEFT   3

----- < Run 1.1 > Configuration#2 -----
Tape#0 : [b]  1   1   1   1 
< Run 1.1 > Applied Command#   3 :   3 ---> BLANK  4 2

----- < Run 1.1 > Configuration#3 -----
Tape#0 : [b]  1   1   1   1 
< Run 1.1 > Applied Command#   4 :   4 ---> WRITE  5

----- < Run 1.1 > Configuration#4 -----
Tape#0 : [1]  1   1   1   1 
< Run 1.1 > Applied Command#   5 :   5 ---> STOP  

< Run 1.1 > Success : Current command (5) is halting one

   -------------------------------------------------------------
   --- < DPM #1, Input #1 >  Result : Input word(s) ACCEPTED ---
   -------------------------------------------------------------

   < DPM #1, Input #1 >  Resource Report
   -------------------------------------
   < DPM #1, Input #1 >  * Input size    :          4 symbols
   < DPM #1, Input #1 >  * Output size   :          5 symbols
   < DPM #1, Input #1 >  * PM-Space used :          5 cells
   < DPM #1, Input #1 >  * PM-Time used  :          4 commands

       |====================|
       |---- Statistics ----|
       |....  Commands  ....|
       |--------------------|
       | Command :    Times |
       |--------------------|
       |       0 :        1 |
       |       1 :        1 |
       |       2 :        1 |
       |       3 :        1 |
       |       4 :        0 |
       |       5 :        0 |
       |--------------------|
       |   Total :        4 |
       |====================|

        %%===========================================
        %%============= Set# 1 :  END  ==============
        %%========= Processing Input Words  =========
        %%===== Nondeterministic Post Machine# 1 ====
        %%===========================================

   Alex Vinokur