The Wayback Machine - https://web.archive.org/web/20080515023814/http://semillon.wpi.edu:80/~aofa/AofA/msg00020.html
ANALYSIS of ALGORITHMS Bulletin Board
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

C++ Simulator of a Turing Machine

Hi,

(Upgraded) C++ Simulator of a Turing Machine can be downloaded at :
* http://alexvn.freeservers.com/s1/turing.html
* http://sourceforge.net/projects/turing-machine/

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

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


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

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


The following demo Turing machines are demonstrated with using the C++ Simulator :
1. An addition program             : Deterministic,     1 tape
2. An addition program with marker : Deterministic,     1 tape
3. A multiplication program        : Deterministic,     1 tape
4. Recognition of palindromes      : Deterministic,     2 tapes
5. Partition problem               : Nondeterministic,  3 tapes
6. Computing Fibonacci numbers     : Deterministic,     1 tape
7. Conversion unary-to-binary      : Deterministic,     1 tape
8. An Euclid algorithm             : Deterministic,     1 tape



Log file fragments are shown below

 -----------------------
 --- File metafile
 -----------------------
   Row#  1 ---> add.dsc 1 add.sta add.abt add.rul add1.in add2.in add3.in add4.in add5.in add6.in add7.in 
   Row#  2 ---> addm.dsc 1 addm.sta add.abt addm.rul add1.in add2.in add3.in add4.in 
   Row#  3 ---> mult.dsc 1 mult.sta mult.abt mult.rul mult1.in mult2.in mult3.in 
   Row#  4 ---> palindr.dsc 2 palindr.sta palindr.abt palindr.rul palindr1.in palindr2.in palindr3.in 
   Row#  5 ---> part.dsc 3 part.sta part.abt part.rul part1.in part2.in part3.in 
   Row#  6 ---> fib.dsc 1 fib.sta fib.abt fib.rul fib1.in fib2.in fib3.in fib5.in fib7.in 
   Row#  7 ---> un2bin.dsc 1 un2bin.sta un2bin.abt un2bin.rul un2bin1.in un2bin2.in un2bin3.in 
   Row#  8 ---> euclid.dsc 1 euclid.sta euclid.abt euclid.rul euclid1.in euclid2.in euclid3.in euclid4.in euclid5.in 
 -----------------------

   ========== Data selected from Metafile metafile ==========
     ---------- Nondeterministic Turing Machine# 1 ----------
      Description file name   : add.dsc
      Number of tapes         : 1
      States file name        : add.sta
      Alphabet file name      : add.abt
      Transitions file name   : add.rul
      Input words files names : add1.in add2.in add3.in add4.in add5.in add6.in add7.in 


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

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

    ====== Description ======
An addition program. 

The program adds two numbers. 
A number 'n' is represented by n 1-s. 
Sample : 
5 is represented as 1 1 1 1 1 
3 is represented as 1 1 1 

Input : Two numbers separated by symbol '*' 
Sample : 
1 1 1 1 1 * 1 1 1 

Output : Resulting number without '*' 
Sample : 
1 1 1 1 1 1 1 1 


    ====== States Definition ======
Initial states  : q0 
Halting states  : qf 
Internal states : q1 q2 


    ====== Alphabet Definition ======
       ------ Tape# 0 ------
Empty symbols alphabet : b 
Input alphabet         : 1 * 
Internal alphabet      : x 



    ====== Transition Rules Definition ======
Rule#   0 :   q0 [ * ] ---> q1 [ (1, N) ]
Rule#   1 :   q0 [ 1 ] ---> q0 [ (1, R) ]
Rule#   2 :   q0 [ b ] ---> q0 [ (b, R) ]
Rule#   3 :   q1 [ 1 ] ---> q1 [ (1, R) ]
Rule#   4 :   q1 [ b ] ---> q2 [ (b, L) ]
Rule#   5 :   q2 [ 1 ] ---> qf [ (b, L) ]

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



        %%===========================================
        %%=== Nondeterministic Turing 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 1 * 1 1 1 ;  Head pos = 0



 ##### < Run 1.1 > Processing #####
 ----- < Run 1.1 > Initial Configuration -----
 State  : q0
Tape#0 : [1]  1   1   1   1   *   1   1   1  
 < Run 1.1 > Applied Rule#   1 :   q0 [ 1 ] ---> q0 [ (1, R) ]


 ----- < Run 1.1 > Configuration#1 -----
 State  : q0
Tape#0 :  1  [1]  1   1   1   *   1   1   1  
 < Run 1.1 > Applied Rule#   1 :   q0 [ 1 ] ---> q0 [ (1, R) ]


 ----- < Run 1.1 > Configuration#2 -----
 State  : q0
Tape#0 :  1   1  [1]  1   1   *   1   1   1  
 < Run 1.1 > Applied Rule#   1 :   q0 [ 1 ] ---> q0 [ (1, R) ]


 ----- < Run 1.1 > Configuration#3 -----
 State  : q0
Tape#0 :  1   1   1  [1]  1   *   1   1   1  
 < Run 1.1 > Applied Rule#   1 :   q0 [ 1 ] ---> q0 [ (1, R) ]


 ----- < Run 1.1 > Configuration#4 -----
 State  : q0
Tape#0 :  1   1   1   1  [1]  *   1   1   1  
 < Run 1.1 > Applied Rule#   1 :   q0 [ 1 ] ---> q0 [ (1, R) ]


 ----- < Run 1.1 > Configuration#5 -----
 State  : q0
Tape#0 :  1   1   1   1   1  [*]  1   1   1  
 < Run 1.1 > Applied Rule#   0 :   q0 [ * ] ---> q1 [ (1, N) ]


 ----- < Run 1.1 > Configuration#6 -----
 State  : q1
Tape#0 :  1   1   1   1   1  [1]  1   1   1  
 < Run 1.1 > Applied Rule#   3 :   q1 [ 1 ] ---> q1 [ (1, R) ]


 ----- < Run 1.1 > Configuration#7 -----
 State  : q1
Tape#0 :  1   1   1   1   1   1  [1]  1   1  
 < Run 1.1 > Applied Rule#   3 :   q1 [ 1 ] ---> q1 [ (1, R) ]


 ----- < Run 1.1 > Configuration#8 -----
 State  : q1
Tape#0 :  1   1   1   1   1   1   1  [1]  1  
 < Run 1.1 > Applied Rule#   3 :   q1 [ 1 ] ---> q1 [ (1, R) ]


 ----- < Run 1.1 > Configuration#9 -----
 State  : q1
Tape#0 :  1   1   1   1   1   1   1   1  [1] 
 < Run 1.1 > Applied Rule#   3 :   q1 [ 1 ] ---> q1 [ (1, R) ]


 ----- < Run 1.1 > Configuration#10 -----
 State  : q1
Tape#0 :  1   1   1   1   1   1   1   1   1  [b] 
 < Run 1.1 > Applied Rule#   4 :   q1 [ b ] ---> q2 [ (b, L) ]


 ----- < Run 1.1 > Configuration#11 -----
 State  : q2
Tape#0 :  1   1   1   1   1   1   1   1  [1] 
 < Run 1.1 > Applied Rule#   5 :   q2 [ 1 ] ---> qf [ (b, L) ]


 ----- < Run 1.1 > Configuration#12 -----
 State  : qf
Tape#0 :  1   1   1   1   1   1   1  [1] 
 < Run 1.1 > Success : Current state (qf) is halting one



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

   < DTM #1, Input #1 >  Resource Report
   -------------------------------------
   < DTM #1, Input #1 >  * Input size    :          9 symbols
   < DTM #1, Input #1 >  * Output size   :          8 symbols
   < DTM #1, Input #1 >  * TM-Space used :         10 cells
   < DTM #1, Input #1 >  * TM-Time used  :         12 transitions



       |==================|
       |--- Statistics ---|
       |... Transition ...|
       |------------------|
       |  Rules :   Times |
       |------------------|
       |      0 :       1 |
       |      1 :       5 |
       |      2 :       0 |
       |      3 :       4 |
       |      4 :       1 |
       |      5 :       1 |
       |------------------|
       |  Total :      12 |
       |==================|

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


   =====================================
   Alex Vinokur
     mailto:alexvn@connect.to
     http://mathforum.org/library/view/10978.html
     news://news.gmane.org/gmane.comp.lang.c++.perfometer
   =====================================