User:Salpynx/Phoney Burn 01
Phoney Burn is a disposable cellular esolang designed to meet the requirements of the Burn reverse engineering challenge.
It devolved out of a serious attempt. Given there is quite a bit of data in the mystery program, there will be more than one way to construct languages that implement Rule 110 using that source, and can be generalised to implement other 1D automata. This takes a minimalist and deliberately over-literal interpretation of the reverse engineering challenge, with tongue firmly in cheek to quickly bash out something that (mostly) works.
Relationship to Burn
I'm confident this is NOT how original Burn worked. Burn looks to be itself a 2D cellular automaton, which can be used to implement 1D CAs. Phoney Burn is not a proper 2D automaton, merely a highly contrived grid based sequential data processor which can be used to implement arbitrary cellular automata (1D elementary CAs at least, up to four states, and maybe extensible to 2D). In the case of the example code, it is a highly contrived rule 110 implementation which uses the required infinite tiling of the rule 110 Turing completeness proof, which is obtained via a most unlikely encoding scheme. I don't know if the Burn Rule 110 program was meant to be a TC proof with the required infinite tiling -- my guess is not, but rather that it was a proof-of-concept to show that a universal 1D CA could be constructed in Burn. I could be wrong, but the easiest way to check would be to ask Burn's creator. Since Phoney Burn was deliberately a creative exercise, it seemed appropriate to choose a significant tiling and force the "data" to decode to that.
It's possible that some of this is unintentionally close to accurate, but it was created as an experiment to show that discovering one of the many possible languages that interpret this code as a Rule 110 implementation is easier than reverse-engineering a specific original one.
Phoney Burn walkthrough
Line 1
00 00 01 00 00 00
The header. 01 indicates a 1D automaton.
Line 2
10 11 01 01 01 11
Definition of our 1D automaton.
Reading right-to-left from the EOL marker 11:
01 indicates the maximum state value a cell can have (1-3)
Subsequent digit pairs show next values of cells surrounded by
00, 01, 10, 11, sequentially for each state from 0 to max state
((0(0)0 => 0) (0(0)1 => 1), (1(0)0 => 0) (1(0)1 => 1) for '0' cells = '01 01' ((0(1)0 => 1) (0(1)1 => 1), (1(1)0 => 1) (1(1)1 => 0) for '1' cells = '11 10'
Combining these RTL gives 10 11 01 01, which is the values from the code example.
The above rules are those of Rule 110.
Lines 3-5
03 20 11 00 00 11 00 00 11 11 11 11 00 00 00 00 00 11
Defines a variable 03 using mode 20 to be used for tiling.
Mode 20 is an unusual encoding method where the doubled 00 and 11 represent the inverse single value, so
00=> 111=> 0
The final 11 in each row is an EOL marker, and not counted as data.
This encoding has the additional peculiarity that, because the data is storing sequential runs of bits, if the next row starts with the same data symbol as the previous data row ended with, it is double-inverted, and a single padding separator bit is added.
11 00 00encodes01100 00 11 11 11starts with00, which ended the previous row, so00 00here encodes001, and11 11 11encodes00000 00 00 00 00encodes11111
Combined, variable 03 = 01100100011111, which is a reversed (and offset) version of one generation of the infinite 14 cell tiling required for the Rule 110 TC proof.
Line 6
10 10 10 10 10 11
Playfield separator.
Line 7
00 00 10 00 00 12
Core part of our playfield definition.
Line 8
00 02 11 00 00 11
Merge the previous row with the 02 rows following the 11 program terminator. The program grid is modified so that this row becomes the result of the merged rows. (I stopped trying so hard at this point, there are multiple ways these rows could be combined.)
Line 9
11 11 11 11 11 11
Program terminator. When encountered, the configuration is complete and the CA will run according to the previously defined rules.
Lines 10-11
00 00 30 00 00 21 00 00 01 01 01 01
Two data rows to be merged.
The row ending in 21 is inverse-associated with the previous row ending in 12 as a substitution rule, to replace the 00 00s of the first row with the reversed data stored in 30 -> 03, which gives:
11111000100110, now the 14 cell tiling required for Rule 110 universality (offset by 9 from what is given at wikipedia:Rule_110#Spaceships_in_Rule_110). The cells are to be tiled infinitely to the left and the right as signified by the 12 21 notation.
The final row (minus the final pair 01, in line with the other rows which also have terminating indicators, 01 => 10) is used to replace the 10 as the starting configuration for the CA to give a starting configuration of:
(11111000100110)*00111(11111000100110)*
Upon reaching the 11 11 11 11 11 11 final terminator row, the CA rules are triggered repeatedly on the previously assembled data row.
This results in a single example of the stable vertical repeating (7 step) structure which is used in the Rule 110 Cyclic Tag System implementation for data strings, which seems like a reasonable simple yet important structure to encode.
