Skip to content

justinba1010/Turing-Machines

BranchesTags

Repository files navigation

Turing-Machines

Multi Symbol

Program uses a key to find list of tuples for each state. Conditions for a turing machine Q should go as a list of {state, conditions}. Conditions are tuples containing read symbol from current spot, the direction, write symbol to current spot and the next state. Following is an example of condition as a tuple, {read symbol, direction, write symbol, next state}.

Note

This program writes the symbol in the current position, then moves the tape. Order is important.

Infinite Tape

Tape is continually added when needed because an infinite tape is not easily representable. An infinite tape will assume an infinite number of zeros before and after the tape.

Busy Beaver through turing_two_symbol

> turing_two_symbol:run([{a, {{r, 1, b}, {l, 1, b}}}, {b, {{l, 1, a},{h, h, h}}}], {[0], [0]}, a).
... 0 0 [1,1,1,1,0] 0 0 ...
ok

Busy Beaver 2 State

> busy_beaver:run().
... 0 0 [1,1,1,1,0] 0 0 ...
ok

Busy Beaver through turing_two_symbol 3 STATE

> turing_two_symbol:run([{a, {{r, 1, b}, {l, 1, c}}}, {b, {{l, 1, a},{r, 1, b}}}, {c, {{l, 1, b}, {h, 1, h}}}], {[0], [0]}, a).
... 0 0 [1,1,1,1,1,1,0] 0 0 ...
ok

Busy Beaver through turing_multi_symbol 3 STATE

> turing_multi_symbol:run([{a, [{0, r, 1, b}, {1, l, 1, c}]}, {b, [{0, l, 1, a}, {1, r, 1, b}]}, {c, [{0, l, 1, b}, {1, h, 1, h}]}], {[0],[0]}, a).      
... 0 0 [1,1,1,1,1,1,0] 0 0 ...

With Debug

>  turing_multi_symbol:run([{a, [{0, r, 1, b}, {1, l, 1, c}]}, {b, [{0, l, 1, a}, {1, r, 1, b}]}, {c, [{0, l, 1, b}, {1, h, 1, h}]}], {[0],[0]}, a, true).
... 0 0 [0,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,0,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,c}
... 0 0 [0,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,b}
... 0 0 [0,1,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,1,b}
... 0 0 [1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,1,b}
... 0 0 [1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,1,b}
... 0 0 [1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,1,b}
... 0 0 [1,1,1,1,1,0,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,c}
... 0 0 [1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,h,1,h}
... 0 0 [1,1,1,1,1,1,0] 0 0 ...

Busy Beaver 4 State

>  turing_multi_symbol:run([{a, [{0, r, 1, b}, {1, l, 1, b}]}, {b, [{0, l, 1, a}, {1, l, 0, c}]}, {c, [{0, h, 1, h}, {1, l, 1, d}]}, {d, [{0, r, 1, d}, {1, r, 0, a}]}], {[0],[0]}, a, true).
... 0 0 [0,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,0,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [0,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [0,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,0,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [0,1,0,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,0,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,0,0,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,0,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,0,1,0,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,0,1,0,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,0,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,0,0,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,0,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,1,0,1,0,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,1,0,1,0,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,1,0,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,1,0,0,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,0,1,0,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,1,0,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [1,1,1,0,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [0,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,0,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,0,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,0,1,0,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,0,1,0,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,0,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,0,0,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,1,0,1,0,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,1,0,1,0,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,1,0,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,1,0,0,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,0,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,1,1,0,1,0,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,1,1,0,1,0,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,1,1,0,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,1,1,0,0,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,1,0,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,1,1,1,0,1,0,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,1,1,1,0,1,0,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,1,1,1,0,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,1,1,1,0,0,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,1,1,0,1,0,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,1,1,1,0,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [1,1,1,1,1,0,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,0,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [1,0,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [0,1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [0,1,1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,0,1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [0,1,0,1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,0,1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,0,0,1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,0,1,1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,0,1,0,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,0,1,0,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,0,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,0,0,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,0,1,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,1,0,1,0,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,1,0,1,0,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,1,0,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,1,0,0,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,0,1,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,1,1,0,1,0,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,1,1,0,1,0,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,1,1,0,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,1,1,0,0,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,1,0,1,0,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,1,1,0,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [1,1,1,1,0,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,1,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [1,1,1,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [0,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [0,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [0,1,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,0,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [0,1,0,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,0,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,0,0,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,0,1,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [1,0,1,0,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,d}
... 0 0 [1,0,1,0,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,d}
... 0 0 [1,1,1,0,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,r,0,a}
... 0 0 [1,1,0,0,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,r,1,b}
... 0 0 [1,1,0,1,0,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,0,1,1,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [1,1,0,1,1,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,l,1,a}
... 0 0 [1,1,1,1,1,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,1,b}
... 0 0 [1,1,1,1,1,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {1,l,0,c}
... 0 0 [0,0,1,1,1,1,1,1,1,1,1,1,1,1,0] 0 0 ...
Current Tape Rule: {0,h,1,h}
... 0 0 [1,0,1,1,1,1,1,1,1,1,1,1,1,1,0] 0 0 ...

About

Turing Machines written in Erlang

Resources

Readme

License

Apache-2.0 license
Activity

Stars

0 stars

Watchers

1 watching

Forks

1 fork
Report repository

Releases

No releases published

Packages

 
 
 

Contributors

Languages