Execute a Markov algorithm: Difference between revisions
Content added Content deleted
(→{{header|C++}}: fixed a bug (the first rule was not reconsidered)) |
(Fifth testcase: Turing machine) |
||
| Line 98: | Line 98: | ||
should generate the output: |
should generate the output: |
||
: <code>11111111111111111111</code> |
: <code>11111111111111111111</code> |
||
'''Ruleset 5:'''<br> |
|||
A simple Turing machine, implementing a three-state busy beaver. The tape consists of 0s and 1s, the states are A, B, C and H (for Halt), and the head position is indicated by writing the state letter before the character where the head is. All parts of the initial tape the machine operates on have to be given in the input. |
|||
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> |
|||
A0 -> 1B |
|||
0A1 -> C01 |
|||
1A1 -> C11 |
|||
0B0 -> A01 |
|||
1B0 -> A11 |
|||
B1 -> 1B |
|||
0C0 -> B01 |
|||
1C0 -> B11 |
|||
0C1 -> H01 |
|||
1C1 -> H11 |
|||
</pre> |
|||
This ruleset should turn |
|||
: <code>000000A000000</code> |
|||
into |
|||
: <code>00011H1111000</code> |
|||
=={{header|C}}== |
=={{header|C}}== |
||