|
|
Boost : |
From: Alex Vinokur (alexvn_at_[hidden])
Date: 2005-02-22 07:03:10
Is there any interest in a library which simulates a deterministic/nondeterminisatic multitape Turing machine?
Current version C++ Simulator of a Turing Machine can be downloaded at :
* http://sourceforge.net/projects/turing-machine/
* http://alexvn.freeservers.com/s1/turing.html
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. An addition program : Deterministic, 2 tapes
4. A multiplication program : Deterministic, 1 tape
5. An Euclid algorithm : Deterministic, 1 tape
6. Recognition of palindromes : Deterministic, 2 tapes
7. Partition problem : Nondeterministic, 3 tapes
8. Conversion unary-to-binary : Deterministic, 1 tape
9. Computing Fibonacci numbers : Deterministic, 1 tape
10. Computing Huffman codes : Deterministic, 3 tapes
Log file fragments are shown below
-----------------------
--- File metafile
-----------------------
add.dsc 1 add.sta add.abt add.rul add1.in add2.in add3.in add4.in add5.in add6.in add7.in
addm.dsc 1 addm.sta add.abt addm.rul add1.in add2.in add3.in add4.in
addt.dsc 2 addt.sta addt.abt addt.rul addt1.in addt2.in
mult.dsc 1 mult.sta mult.abt mult.rul mult1.in mult2.in mult3.in
euclid.dsc 1 euclid.sta euclid.abt euclid.rul euclid1.in euclid2.in euclid3.in euclid4.in euclid5.in
palindr.dsc 2 palindr.sta palindr.abt palindr.rul palindr1.in palindr2.in palindr3.in
part.dsc 3 part.sta part.abt part.rul part1.in part2.in part3.in
un2bin.dsc 1 un2bin.sta un2bin.abt un2bin.rul un2bin1.in un2bin2.in un2bin3.in
fib.dsc 1 fib.sta fib.abt fib.rul fib1.in fib2.in fib3.in fib5.in fib7.in
huffman.dsc 3 huffman.sta huffman.abt huffman.rul equ.in fib.in arb.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
email: alex DOT vinokur AT gmail DOT com
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk