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