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
========== 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'
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