0
I Use This!
Activity Not Available

Project Summary

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 :
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 ====
%%===========================================

Tags

No tags have been added

In a Nutshell, C++ Simulator of a Turing Machine...

 No code available to analyze

Open Hub computes statistics on FOSS projects by examining source code and commit history in source code management systems. This project has no code locations, and so Open Hub cannot perform this analysis

Is this project's source code hosted in a publicly available repository? Do you know the URL? If you do, click the button below and tell us so that Open Hub can generate statistics! It's fast and easy - try it and see!

Add a code location

GNU General Public License v2.0 or later
Permitted

Commercial Use

Modify

Distribute

Place Warranty

Forbidden

Sub-License

Hold Liable

Required

Distribute Original

Disclose Source

Include Copyright

State Changes

Include License

These details are provided for information only. No information here is legal advice and should not be used as such.

All Licenses

This Project has No vulnerabilities Reported Against it

Did You Know...

  • ...
    there are over 3,000 projects on the Open Hub with security vulnerabilities reported against them
  • ...
    you can subscribe to e-mail newsletters to receive update from the Open Hub blog
  • ...
    nearly 1 in 3 companies have no process for identifying, tracking, or remediating known open source vulnerabilities
  • ...
    anyone with an Open Hub account can update a project's tags

 No code available to analyze

Open Hub computes statistics on FOSS projects by examining source code and commit history in source code management systems. This project has no code locations, and so Open Hub cannot perform this analysis

Is this project's source code hosted in a publicly available repository? Do you know the URL? If you do, click the button below and tell us so that Open Hub can generate statistics! It's fast and easy - try it and see!

Add a code location

Community Rating

Be the first to rate this project
Click to add your rating
   Spinner
Review this Project!
Sample ohloh analysis