C++ Simulator of a Turing Machine - Summary
This group 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
Powered by Savane 3.13-3230.
Corresponding source code