Execute a Markov algorithm: Difference between revisions
Content added Content deleted
(Fifth testcase: Turing machine) |
(added comments to turing ruleset) |
||
| Line 104: | Line 104: | ||
Besides demonstrating that the Markov algorithm is Turing-complete, it also made me catch a bug in the C++ implementation which wasn't caught by the first four rulesets. |
Besides demonstrating that the Markov algorithm is Turing-complete, it also made me catch a bug in the C++ implementation which wasn't caught by the first four rulesets. |
||
<pre> |
<pre> |
||
# Turing machine: three-state busy beaver |
|||
# |
|||
# state A, symbol 0 => write 1, move right, new state B |
|||
A0 -> 1B |
A0 -> 1B |
||
# state A, symbol 1 => write 1, move left, new state C |
|||
0A1 -> C01 |
0A1 -> C01 |
||
1A1 -> C11 |
1A1 -> C11 |
||
# state B, symbol 0 => write 1, move left, new state A |
|||
0B0 -> A01 |
0B0 -> A01 |
||
1B0 -> A11 |
1B0 -> A11 |
||
# state B, symbol 1 => write 1, move right, new state B |
|||
B1 -> 1B |
B1 -> 1B |
||
# state C, symbol 0 => write 1, move left, new state B |
|||
0C0 -> B01 |
0C0 -> B01 |
||
1C0 -> B11 |
1C0 -> B11 |
||
# state C, symbol 1 => write 1, move left, halt |
|||
0C1 -> H01 |
0C1 -> H01 |
||
1C1 -> H11 |
1C1 -> H11 |
||