Turing machine implementation in Java.
The executable takes as an argument the machine definition and starts the machine.
To build the JAR run:
mvn package
To run the machine (with one of the examples) run:
java -jar target/turing.jar examples/rule110/random-tape
This will run rule 110 which is the smallest (3 symbols, 2 states) complete turing automation.
java -jar turing.jar machine_definition_file [number_of_iterations]
* machine_definition_file - is the definition of the Turing Machine to execute
* number_of_iterations - number of iteration to execute (optional). If not specified,
the machine will go on forever or until it reaches HALT state or an error occurs.
The machine can be defined as a simple text file with the following structure:
<machine name>
INFINITE_TAPE: <true|false> - is the tape infinite (in both directions)
TAPE: <the initial tape state> - each state is separated with | (pipe)
DEAFULT_TAPE_SYMBOL: <symbol> - the default symbol with which the tape is populated, when infinite tape is used
TAPE_POSITION: <number> - initial position of the machine's head on the tape
START_STATE: <state> - initial state of the machine
<machine rule table> - a table containing the rules for the machine in the following format:
<symbol0> = <state0>: <write_symbol>,<move_in_direction>,<set_state> | <state1>: <write_symbol>,<move_in_direction>,<set_state> | ... | <stateN>: <write_symbol>,<move_in_direction>,<set_state>
<symbol1> = <state0>: <write_symbol>,<move_in_direction>,<set_state> | <state1>: <write_symbol>,<move_in_direction>,<set_state> | ... | <stateN>: <write_symbol>,<move_in_direction>,<set_state>
...
<symbolM> = <state0>: <write_symbol>,<move_in_direction>,<set_state> | <state1>: <write_symbol>,<move_in_direction>,<set_state> | ... | <stateN>: <write_symbol>,<move_in_direction>,<set_state>
Where:
symbolM - is the M-th symbol of the machine
stateN - is the N-th state of the machine
write_symbol - is the symbol to be written on the place where the head is, before moving on
move_in_direction - -1 to move th head 1 cell left, 1 to move the head 1 cell right
set_state - set the machine state to <state> before moving
Here is a working example of a Turing machine - 2 states (A,B), 3 symbols (+,-,#), infinite tape with "-" as a default symbol:
Rule 101
INFINITE_TAPE: true
TAPE: -|-|+|+|+|-|-|#|+|#|-|-|-|-|+|-
DEAFULT_TAPE_SYMBOL: -
TAPE_POSITION: 8
START_STATE: A
-= A: +, 1,B | B: #,-1,A
+= A: #,-1,A | B: #, 1,B
#= A: +,-1,A | B: -, 1,A
The machine will output a header before it starts the computation itself.
The header looks like this:
Machine: Rule 101
Symbols: [#, +, -]
States: [A, B]
Start State: A
Blank symbol: -
Rules table:
+--------+---------------+---------------+
| | A| B|
+--------+---------------+---------------+
| #| +, L, A| -, R, A|
+--------+---------------+---------------+
| +| #, L, A| #, R, B|
+--------+---------------+---------------+
| -| +, R, B| #, L, A|
+--------+---------------+---------------+
As you can see, the machine name, symbols, possible states, the initial state, blank (default) symbol, and the rules table will be printed out. Then, for each iteration (including the inital state) exactly one line is printed in the following format:
{iteration number}. ({current_state}) {tape dump}
where the {tape_dump} looks like this:
[{cell0 symbol}][{cell1 symbol}]...>{the head is currently positioned here}<...[{cellN symbol}]
for example the following line:
59. (A) [-][+][+][#][+][#][+][#][#][#][-]>#<[+][#][+][-]
is the 59th iteration; the state of the machine at that point is A and the head points at the 11th cell (0-based) at a # (>#<).
Rule 110
Here are the first 100 iterations of the "Rule 100" Turing machine with random populated tape:
$ java -jar target/turing.jar examples/rule110/random-tape 100
Machine: Rule 101
Symbols: [#, +, -]
States: [A, B]
Start State: A
Blank symbol: -
Rules table:
+--------+---------------+---------------+
| | A| B|
+--------+---------------+---------------+
| #| +, L, A| -, R, A|
+--------+---------------+---------------+
| +| #, L, A| #, R, B|
+--------+---------------+---------------+
| -| +, R, B| #, L, A|
+--------+---------------+---------------+
Initial state:
0. (A) [-][-][+][+][+][-][-][#]>+<[#][-][-][-][-][+][-]
====== COMPUTATION BEGIN ========
1. (A) [-][-][+][+][+][-][-]>#<[#][#][-][-][-][-][+][-]
2. (A) [-][-][+][+][+][-]>-<[+][#][#][-][-][-][-][+][-]
3. (B) [-][-][+][+][+][-][+]>+<[#][#][-][-][-][-][+][-]
4. (B) [-][-][+][+][+][-][+][#]>#<[#][-][-][-][-][+][-]
5. (A) [-][-][+][+][+][-][+][#][-]>#<[-][-][-][-][+][-]
6. (A) [-][-][+][+][+][-][+][#]>-<[+][-][-][-][-][+][-]
7. (B) [-][-][+][+][+][-][+][#][+]>+<[-][-][-][-][+][-]
8. (B) [-][-][+][+][+][-][+][#][+][#]>-<[-][-][-][+][-]
9. (A) [-][-][+][+][+][-][+][#][+]>#<[#][-][-][-][+][-]
10. (A) [-][-][+][+][+][-][+][#]>+<[+][#][-][-][-][+][-]
11. (A) [-][-][+][+][+][-][+]>#<[#][+][#][-][-][-][+][-]
12. (A) [-][-][+][+][+][-]>+<[+][#][+][#][-][-][-][+][-]
13. (A) [-][-][+][+][+]>-<[#][+][#][+][#][-][-][-][+][-]
14. (B) [-][-][+][+][+][+]>#<[+][#][+][#][-][-][-][+][-]
15. (A) [-][-][+][+][+][+][-]>+<[#][+][#][-][-][-][+][-]
16. (A) [-][-][+][+][+][+]>-<[#][#][+][#][-][-][-][+][-]
17. (B) [-][-][+][+][+][+][+]>#<[#][+][#][-][-][-][+][-]
18. (A) [-][-][+][+][+][+][+][-]>#<[+][#][-][-][-][+][-]
19. (A) [-][-][+][+][+][+][+]>-<[+][+][#][-][-][-][+][-]
20. (B) [-][-][+][+][+][+][+][+]>+<[+][#][-][-][-][+][-]
21. (B) [-][-][+][+][+][+][+][+][#]>+<[#][-][-][-][+][-]
22. (B) [-][-][+][+][+][+][+][+][#][#]>#<[-][-][-][+][-]
23. (A) [-][-][+][+][+][+][+][+][#][#][-]>-<[-][-][+][-]
24. (B) [-][-][+][+][+][+][+][+][#][#][-][+]>-<[-][+][-]
25. (A) [-][-][+][+][+][+][+][+][#][#][-]>+<[#][-][+][-]
26. (A) [-][-][+][+][+][+][+][+][#][#]>-<[#][#][-][+][-]
27. (B) [-][-][+][+][+][+][+][+][#][#][+]>#<[#][-][+][-]
28. (A) [-][-][+][+][+][+][+][+][#][#][+][-]>#<[-][+][-]
29. (A) [-][-][+][+][+][+][+][+][#][#][+]>-<[+][-][+][-]
30. (B) [-][-][+][+][+][+][+][+][#][#][+][+]>+<[-][+][-]
31. (B) [-][-][+][+][+][+][+][+][#][#][+][+][#]>-<[+][-]
32. (A) [-][-][+][+][+][+][+][+][#][#][+][+]>#<[#][+][-]
33. (A) [-][-][+][+][+][+][+][+][#][#][+]>+<[+][#][+][-]
34. (A) [-][-][+][+][+][+][+][+][#][#]>+<[#][+][#][+][-]
35. (A) [-][-][+][+][+][+][+][+][#]>#<[#][#][+][#][+][-]
36. (A) [-][-][+][+][+][+][+][+]>#<[+][#][#][+][#][+][-]
37. (A) [-][-][+][+][+][+][+]>+<[+][+][#][#][+][#][+][-]
38. (A) [-][-][+][+][+][+]>+<[#][+][+][#][#][+][#][+][-]
39. (A) [-][-][+][+][+]>+<[#][#][+][+][#][#][+][#][+][-]
40. (A) [-][-][+][+]>+<[#][#][#][+][+][#][#][+][#][+][-]
41. (A) [-][-][+]>+<[#][#][#][#][+][+][#][#][+][#][+][-]
42. (A) [-][-]>+<[#][#][#][#][#][+][+][#][#][+][#][+][-]
43. (A) [-]>-<[#][#][#][#][#][#][+][+][#][#][+][#][+][-]
44. (B) [-][+]>#<[#][#][#][#][#][+][+][#][#][+][#][+][-]
45. (A) [-][+][-]>#<[#][#][#][#][+][+][#][#][+][#][+][-]
46. (A) [-][+]>-<[+][#][#][#][#][+][+][#][#][+][#][+][-]
47. (B) [-][+][+]>+<[#][#][#][#][+][+][#][#][+][#][+][-]
48. (B) [-][+][+][#]>#<[#][#][#][+][+][#][#][+][#][+][-]
49. (A) [-][+][+][#][-]>#<[#][#][+][+][#][#][+][#][+][-]
50. (A) [-][+][+][#]>-<[+][#][#][+][+][#][#][+][#][+][-]
51. (B) [-][+][+][#][+]>+<[#][#][+][+][#][#][+][#][+][-]
52. (B) [-][+][+][#][+][#]>#<[#][+][+][#][#][+][#][+][-]
53. (A) [-][+][+][#][+][#][-]>#<[+][+][#][#][+][#][+][-]
54. (A) [-][+][+][#][+][#]>-<[+][+][+][#][#][+][#][+][-]
55. (B) [-][+][+][#][+][#][+]>+<[+][+][#][#][+][#][+][-]
56. (B) [-][+][+][#][+][#][+][#]>+<[+][#][#][+][#][+][-]
57. (B) [-][+][+][#][+][#][+][#][#]>+<[#][#][+][#][+][-]
58. (B) [-][+][+][#][+][#][+][#][#][#]>#<[#][+][#][+][-]
59. (A) [-][+][+][#][+][#][+][#][#][#][-]>#<[+][#][+][-]
60. (A) [-][+][+][#][+][#][+][#][#][#]>-<[+][+][#][+][-]
61. (B) [-][+][+][#][+][#][+][#][#][#][+]>+<[+][#][+][-]
62. (B) [-][+][+][#][+][#][+][#][#][#][+][#]>+<[#][+][-]
63. (B) [-][+][+][#][+][#][+][#][#][#][+][#][#]>#<[+][-]
64. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#][-]>+<[-]
65. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#]>-<[#][-]
66. (B) [-][+][+][#][+][#][+][#][#][#][+][#][#][+]>#<[-]
67. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][-]>-<
68. (B) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][-][+]>-<
69. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][-]>+<[#]
70. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#][+]>-<[#][#]
71. (B) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][+]>#<[#]
72. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][+][-]>#<
73. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][+]>-<[+]
74. (B) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][+][+]>+<
75. (B) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][+][+][#]>-<
76. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][+][+]>#<[#]
77. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#][+][+]>+<[+][#]
78. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#][+]>+<[#][+][#]
79. (A) [-][+][+][#][+][#][+][#][#][#][+][#][#]>+<[#][#][+][#]
80. (A) [-][+][+][#][+][#][+][#][#][#][+][#]>#<[#][#][#][+][#]
81. (A) [-][+][+][#][+][#][+][#][#][#][+]>#<[+][#][#][#][+][#]
82. (A) [-][+][+][#][+][#][+][#][#][#]>+<[+][+][#][#][#][+][#]
83. (A) [-][+][+][#][+][#][+][#][#]>#<[#][+][+][#][#][#][+][#]
84. (A) [-][+][+][#][+][#][+][#]>#<[+][#][+][+][#][#][#][+][#]
85. (A) [-][+][+][#][+][#][+]>#<[+][+][#][+][+][#][#][#][+][#]
86. (A) [-][+][+][#][+][#]>+<[+][+][+][#][+][+][#][#][#][+][#]
87. (A) [-][+][+][#][+]>#<[#][+][+][+][#][+][+][#][#][#][+][#]
88. (A) [-][+][+][#]>+<[+][#][+][+][+][#][+][+][#][#][#][+][#]
89. (A) [-][+][+]>#<[#][+][#][+][+][+][#][+][+][#][#][#][+][#]
90. (A) [-][+]>+<[+][#][+][#][+][+][+][#][+][+][#][#][#][+][#]
91. (A) [-]>+<[#][+][#][+][#][+][+][+][#][+][+][#][#][#][+][#]
92. (A) >-<[#][#][+][#][+][#][+][+][+][#][+][+][#][#][#][+][#]
93. (B) [+]>#<[#][+][#][+][#][+][+][+][#][+][+][#][#][#][+][#]
94. (A) [+][-]>#<[+][#][+][#][+][+][+][#][+][+][#][#][#][+][#]
95. (A) [+]>-<[+][+][#][+][#][+][+][+][#][+][+][#][#][#][+][#]
96. (B) [+][+]>+<[+][#][+][#][+][+][+][#][+][+][#][#][#][+][#]
97. (B) [+][+][#]>+<[#][+][#][+][+][+][#][+][+][#][#][#][+][#]
98. (B) [+][+][#][#]>#<[+][#][+][+][+][#][+][+][#][#][#][+][#]
99. (A) [+][+][#][#][-]>+<[#][+][+][+][#][+][+][#][#][#][+][#]
100. (A) [+][+][#][#]>-<[#][#][+][+][+][#][+][+][#][#][#][+][#]
====== COMPUTATION END ========
Computation complete. . .
The first 100 iterations of the same machine starting with blank tape:
$ java -jar target/turing.jar examples/rule110/empty-tape 100
Machine: Rule 101
Symbols: [#, +, -]
States: [A, B]
Start State: A
Blank symbol: -
Rules table:
+--------+---------------+---------------+
| | A| B|
+--------+---------------+---------------+
| #| +, L, A| -, R, A|
+--------+---------------+---------------+
| +| #, L, A| #, R, B|
+--------+---------------+---------------+
| -| +, R, B| #, L, A|
+--------+---------------+---------------+
Initial state:
0. (A) >-<
====== COMPUTATION BEGIN ========
1. (B) [+]>-<
2. (A) >+<[#]
3. (A) >-<[#][#]
4. (B) [+]>#<[#]
5. (A) [+][-]>#<
6. (A) [+]>-<[+]
7. (B) [+][+]>+<
8. (B) [+][+][#]>-<
9. (A) [+][+]>#<[#]
10. (A) [+]>+<[+][#]
11. (A) >+<[#][+][#]
12. (A) >-<[#][#][+][#]
13. (B) [+]>#<[#][+][#]
14. (A) [+][-]>#<[+][#]
15. (A) [+]>-<[+][+][#]
16. (B) [+][+]>+<[+][#]
17. (B) [+][+][#]>+<[#]
18. (B) [+][+][#][#]>#<
19. (A) [+][+][#][#][-]>-<
20. (B) [+][+][#][#][-][+]>-<
21. (A) [+][+][#][#][-]>+<[#]
22. (A) [+][+][#][#]>-<[#][#]
23. (B) [+][+][#][#][+]>#<[#]
24. (A) [+][+][#][#][+][-]>#<
25. (A) [+][+][#][#][+]>-<[+]
26. (B) [+][+][#][#][+][+]>+<
27. (B) [+][+][#][#][+][+][#]>-<
28. (A) [+][+][#][#][+][+]>#<[#]
29. (A) [+][+][#][#][+]>+<[+][#]
30. (A) [+][+][#][#]>+<[#][+][#]
31. (A) [+][+][#]>#<[#][#][+][#]
32. (A) [+][+]>#<[+][#][#][+][#]
33. (A) [+]>+<[+][+][#][#][+][#]
34. (A) >+<[#][+][+][#][#][+][#]
35. (A) >-<[#][#][+][+][#][#][+][#]
36. (B) [+]>#<[#][+][+][#][#][+][#]
37. (A) [+][-]>#<[+][+][#][#][+][#]
38. (A) [+]>-<[+][+][+][#][#][+][#]
39. (B) [+][+]>+<[+][+][#][#][+][#]
40. (B) [+][+][#]>+<[+][#][#][+][#]
41. (B) [+][+][#][#]>+<[#][#][+][#]
42. (B) [+][+][#][#][#]>#<[#][+][#]
43. (A) [+][+][#][#][#][-]>#<[+][#]
44. (A) [+][+][#][#][#]>-<[+][+][#]
45. (B) [+][+][#][#][#][+]>+<[+][#]
46. (B) [+][+][#][#][#][+][#]>+<[#]
47. (B) [+][+][#][#][#][+][#][#]>#<
48. (A) [+][+][#][#][#][+][#][#][-]>-<
49. (B) [+][+][#][#][#][+][#][#][-][+]>-<
50. (A) [+][+][#][#][#][+][#][#][-]>+<[#]
51. (A) [+][+][#][#][#][+][#][#]>-<[#][#]
52. (B) [+][+][#][#][#][+][#][#][+]>#<[#]
53. (A) [+][+][#][#][#][+][#][#][+][-]>#<
54. (A) [+][+][#][#][#][+][#][#][+]>-<[+]
55. (B) [+][+][#][#][#][+][#][#][+][+]>+<
56. (B) [+][+][#][#][#][+][#][#][+][+][#]>-<
57. (A) [+][+][#][#][#][+][#][#][+][+]>#<[#]
58. (A) [+][+][#][#][#][+][#][#][+]>+<[+][#]
59. (A) [+][+][#][#][#][+][#][#]>+<[#][+][#]
60. (A) [+][+][#][#][#][+][#]>#<[#][#][+][#]
61. (A) [+][+][#][#][#][+]>#<[+][#][#][+][#]
62. (A) [+][+][#][#][#]>+<[+][+][#][#][+][#]
63. (A) [+][+][#][#]>#<[#][+][+][#][#][+][#]
64. (A) [+][+][#]>#<[+][#][+][+][#][#][+][#]
65. (A) [+][+]>#<[+][+][#][+][+][#][#][+][#]
66. (A) [+]>+<[+][+][+][#][+][+][#][#][+][#]
67. (A) >+<[#][+][+][+][#][+][+][#][#][+][#]
68. (A) >-<[#][#][+][+][+][#][+][+][#][#][+][#]
69. (B) [+]>#<[#][+][+][+][#][+][+][#][#][+][#]
70. (A) [+][-]>#<[+][+][+][#][+][+][#][#][+][#]
71. (A) [+]>-<[+][+][+][+][#][+][+][#][#][+][#]
72. (B) [+][+]>+<[+][+][+][#][+][+][#][#][+][#]
73. (B) [+][+][#]>+<[+][+][#][+][+][#][#][+][#]
74. (B) [+][+][#][#]>+<[+][#][+][+][#][#][+][#]
75. (B) [+][+][#][#][#]>+<[#][+][+][#][#][+][#]
76. (B) [+][+][#][#][#][#]>#<[+][+][#][#][+][#]
77. (A) [+][+][#][#][#][#][-]>+<[+][#][#][+][#]
78. (A) [+][+][#][#][#][#]>-<[#][+][#][#][+][#]
79. (B) [+][+][#][#][#][#][+]>#<[+][#][#][+][#]
80. (A) [+][+][#][#][#][#][+][-]>+<[#][#][+][#]
81. (A) [+][+][#][#][#][#][+]>-<[#][#][#][+][#]
82. (B) [+][+][#][#][#][#][+][+]>#<[#][#][+][#]
83. (A) [+][+][#][#][#][#][+][+][-]>#<[#][+][#]
84. (A) [+][+][#][#][#][#][+][+]>-<[+][#][+][#]
85. (B) [+][+][#][#][#][#][+][+][+]>+<[#][+][#]
86. (B) [+][+][#][#][#][#][+][+][+][#]>#<[+][#]
87. (A) [+][+][#][#][#][#][+][+][+][#][-]>+<[#]
88. (A) [+][+][#][#][#][#][+][+][+][#]>-<[#][#]
89. (B) [+][+][#][#][#][#][+][+][+][#][+]>#<[#]
90. (A) [+][+][#][#][#][#][+][+][+][#][+][-]>#<
91. (A) [+][+][#][#][#][#][+][+][+][#][+]>-<[+]
92. (B) [+][+][#][#][#][#][+][+][+][#][+][+]>+<
93. (B) [+][+][#][#][#][#][+][+][+][#][+][+][#]>-<
94. (A) [+][+][#][#][#][#][+][+][+][#][+][+]>#<[#]
95. (A) [+][+][#][#][#][#][+][+][+][#][+]>+<[+][#]
96. (A) [+][+][#][#][#][#][+][+][+][#]>+<[#][+][#]
97. (A) [+][+][#][#][#][#][+][+][+]>#<[#][#][+][#]
98. (A) [+][+][#][#][#][#][+][+]>+<[+][#][#][+][#]
99. (A) [+][+][#][#][#][#][+]>+<[#][+][#][#][+][#]
100. (A) [+][+][#][#][#][#]>+<[#][#][+][#][#][+][#]
====== COMPUTATION END ========
Computation complete. . .