C++ Simulator of a Post Machine

["Alex Vinokur" <alexvn@xxxxxxxxxx>]

Hi,

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
     mailto:alexvn@connect.to
     http://mathforum.org/library/view/10978.html
     news://news.gmane.org/gmane.comp.lang.c++.perfometer
   =====================================