ta-sa.org - Tm.C

(best viewed in any resolution with any HTML enabled browser)

Main:
Index
Contact
Links

Studies:
Informatics
Scripts
Material

Projects:
Git repository

Programs:
cdplay
ECMS
lip.C
baseclc.c
nfa-util.C
tm.C
termreplace
psi_pw_decode
bummskraut

Perl:
AnyEvent::XMPP
Net::XMPP2
AnyEvent::IRC
Object::Event
AnyEvent::HTTPD
AnyEvent::EditText
MIDI::Sequencer

Music:
Ta-Sa Music
Languages:
LR Grammar Collection

Deliantra:
Deliantra

GNU Smalltalk:
Links

Other:
Laughing man logo
ta-sa.org

Java must DIE

Tm.C - last change: added the rest of the content for the new website, Sat Apr 5 16:42:15 2008 +0200

tm.C - a one tape Turing machine interpreter

tm.C is a simple one tape Turing machine interpreter. It takes the definition of the Turing machine from a file and will read a band initialisation from standart input.
After reading everything, it start execution and prints the current configuration of the turing machine before each step.

Note: When printing the configuration any leading filling characters on the band, and all never visited cells on the tail are suppresed. Also note that if you have moved with the head far out to the right and only left blanks there, that they will be printed. This maybe changes in later versions.

Note 2: When allocating new memory for the tape it does allocate 10 more cells every time, and these will be shown when printing the configuration.

Note 3: You are free to construct a endless running turing machine. But keep in mind that it might run out of memory.

Note 4: You have to define all possible state and input characters or the turing machine will interrupt execution and exit with an error message

Note 5: The code is a little bit messy, but it works. It also lacks any comments, i will maybe add some if anyone is interested or i find the time to comment it.

If you experience any problems or if you have questions, feel free to ask me via mail: elmex@ta-sa.org or contact me in any other way.

News

8.12.2005 - 17:51:	I uploaded a new version of tm.C. I implemented start settings (and a command line interface for it)

Input file format

The inputfile is a simple ASCII file. An example would be:

fill=' '
=> q0
:a|a,L => w1

=> q1
:a|b,R => q1
: | ,N => q1

=> w1
: |a,N => q1

The first lines sets the fill character for the band and the start state of the TM. (For an example of usage of the start_setting look in the Example 2)

Note: You can also set the start_settings via command line.

Note 2: The start-position 0 is at the beginning of the band-input (given via stdin). A negative position will move the head out in to blanks on the left of the input and a positive position will move the head right into the input.

BNF for the first lines (fill_setting, start_setting):

state_name         ::= <character>+
start_state        ::= <state-name>

fill_character     ::= <character>

fill_setting       ::= 'fill' <whitespace>* '=' <whitespace>* '\'' <fill_character> '\''
start_setting      ::= '@' <whitespace>* ['-'] <digits>+ ',' <start_state>

A state definition begins always with a '=>' followed by the state name. The state transition rules start with ':'.
Here a BNF (the main constructs are state_definition and state_transition):

input_character    ::= <character>
output_character   ::= <character>
head_direction     ::= 'r' | 'R' | 'l' | 'L' | 'n' | 'N'

state_definition   ::= '=>' <whitespace>* <state_name>
state_transition   ::= ':' <input_character> '|' <output_character> ',' <head_direction> <whitespace>* '=>' <whitespace>* <state_name>

As the BNF describes, the first character before the first '|' (pipe) is the input character, which is the expected character on the tape. The character after the '|' is the output character, which will be written to the tape before moving the head and going to the next state. The direction of the head movement is the character after the ',', it can be 'r' or 'R' for right, 'l' or 'L' for left and 'n' or 'N' for no movement at all. The next state is given after the '=>'.

Command Line Parameters:

root@kiste: ~# ./tm
usage: tmeval <machinedef-file> [<start-pos> [<start-state>]]

The TM interpreter takes 3 commandline arguments:

The machinedef-file (for the format see above and the examples)
The start position of the head (can also be defined in the machinedef)
The start state (can also be defined in the machinedef)

Note: The command line arguments for start position and start state override the start_setting in the machinedef.

Download:

tm.C

Example:

Build it with:

# g++ tm.C -o tm

Example run (with the above turing machine definition):

# echo "aaaaa" | ./tm test.tm
Reading Machine definition from: test.tm
reading turing machine definition:
Start State: q0
=> q0
:a|a,L => w1
=> q1
:a|b,R => q1
: | ,N => q1
=> w1
: |a,N => q1
finished reading turing machine definition
band:
aaaaa 
(q0)aaaaa 
(w1) aaaaa 
(q1)aaaaaa 
b(q1)aaaaa 
bb(q1)aaaa 
bbb(q1)aaa 
bbbb(q1)aa 
bbbbb(q1)a 
bbbbbb(q1)           
machine halted at position 5 on char ' ' in state: q1
band after execution:
bbbbbb           

And a sample run with less information:

# echo "aaaaa" | ./tm test.tm 2> /dev/null
aaaaa 
(q0)aaaaa 
(w1) aaaaa 
(q1)aaaaaa 
b(q1)aaaaa 
bb(q1)aaaa 
bbb(q1)aaa 
bbbb(q1)aa 
bbbbb(q1)a 
bbbbbb(q1)           
bbbbbb

Example 2:

root@kiste: ~# cat tm2.tm
fill='_'
@1,s
=> s
:a|_,R => a
:b|_,R => b

=> a
:a|a,R => a
:_|a,L => B
:b|a,R => b

=> b
:b|b,R => b
:_|b,L => B
:a|b,R => a

=> B
:a|a,L => B
:b|b,L => B
:_|_,R => E

=> E
:_|_,N => E
:b|b,N => E
:a|a,N => E
root@kiste: ~# echo "aabbaa" | ./tm tm2.tm 3
Reading Machine definition from: tm2.tm
reading turing machine definition:
set fill character: '_'
Start State: s
=> s
:a|_,R => a
:b|_,R => b
=> a
:a|a,R => a
:_|a,L => B
:b|a,R => b
=> b
:b|b,R => b
:_|b,L => B
:a|b,R => a
=> B
:a|a,L => B
:b|b,L => B
:_|_,R => E
=> E
:_|_,N => E
:b|b,N => E
:a|a,N => E
finished reading turing machine definition
band:
aabbaa_
aab(s)baa_
aab_(b)aa_
aab_b(a)a_
aab_ba(a)___________
aab_b(B)aa__________
aab_(B)baa__________
aab(B)_baa__________
aab_(E)baa__________
machine halted at position 4 on char 'b' in state: E

band after execution:
aab_baa__________

All logos and trademarks on this site are property of their respective owner. Site admin is: elmex@ta-sa.org