mainC++ Simulator of a Turing Machine - Summary

 
 
Membership Info
Project Admin:
1 active member

Group identification
Id: #5764
System Name: turing-mach
Name: C++ Simulator of a Turing Machine
Group Type: non-GNU software and documentation

Search in this Group

in
   

This project is not part of the GNU Project.

C++ Simulator of a Turing Machine can be downloaded at :

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 setup files and 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 ====
        %%===========================================

Registration Date: Thu 27 Nov 2003 05:09:20 AM UTC
License: GNU General Public License v2 or later
Development Status: 5 - Production/Stable

 

Latest News rss feed

Communication Tools
 Mailing Lists (0 public mailing lists)

Development Tools

Back to the top


Powered by Savane 3.7