User:Salpynx/Burn

Analysis of the Burn Rule 110 program

Some basic propositions:

• The 6x11 patch is tiled infintely in a 2D plane as per the hints.
• The 6x11 patch must contain at least one simulated Rule 110 cell

Rule110 structure:

• 1D cellular automata require a 1D current state (binary string) extending infinitely in both directions
• Subsequent generations progress orthogonally in a third direction
• This requires a 2D field with one privileged direction (an "arrow of time")
• The Burn constraint that cells cannot ever return to a previous state means that the current -> next dimension is NOT time, it must be a physical direction.
• Burn's infinite 2D grid is sufficient to accommodate this.
• Burn itself as a 2D automaton should not have a privileged direction, this 1D automaton arrow of time must be provided _solely_ by the Rule110 source

Initial Rule110 seed:

• There is no point for the initial state to include more than one row (i.e. past generations) -- it would waste space and have no effect
• An initial seed state must have at least one ON cell (otherwise the system would not evolve because 000 -> 0)
• An initial seed cannot consist of an infinite tiling of the same cell. All 1s -> All 0s -> Inactive halt state. This applies to a full 2D titling, or a single row of all 1s.
• Alternating '01' also ends in a full zero state
• An alternating 3 length patterns ('001' or '110', with identical offset variation) also quickly converges to all 0s
• I haven't looked at 4 length patterns, but a repeated seed will need to be at least 4 cells wide to do anything interesting, and we are running out of room in the 6x11 patch
• Conclusion: The most practical and interesting seed state is a single ON cell, sitting in the middle of an infinite field of OFF or neutral cells
• This suggests there is a privileged seed 6x11 patch which is initialised ON to begin the computation, while the remaining tiled patches are different.
• This could be accomplished either by some features of the 6x11 being split between seed and tile patches, or some features not transferred to the tiled copies, or by there being some convention to act on the seed tile in a particular way to kickstart the computation. Perhaps there is a region around the seed where some (not all) values are decremented until they reach zero?

At any rate, the requirements of a Rule110 program suggest Burn MUST treat a seed patch differently from its tiled clones in order for a useful computation to take place. I believe this is the 'disrupted slightly' mentioned in the original hints, and some form is required:

...it's used to tile an entire infinite plane (possibly disrupted slightly; I can't remember);

As a stating point, we can take the coloured image of the Rule110 source, choose an current->next direction of N->S. There is no reason to assume it's necessarily N->S, it could be S->N, or even E/W W/E, but N->S seems a sensible convention, and the fact that there is a single wire `01` surrounded by `00` on the north edge suggests a vertical entry/exit point, so vertical is more likely than horizontal. Let's work with N->S until we can find something that eliminates it as a possibility.

Putting aside how Burn might initialise the seed cell when tiling, lets look at the program's Rule110 cell structure, which we have concluded only represents one Rule110 cell.

We can assume the previous state is transferred from the North on the single wire touching the North edge. It's hard to decide what all the colours mean, but the majority of 01, 10, and 11 cells, contrasted with empty 00 cells suggest 'wires'. Somewhat ignoring the specifics of what the other colours represent we can still analyse the paths and junctions of the program.

Burn Rule110 program tiled and numbered.

If we flood fill the wires from the North edge in incremental steps, we can get an idea of data flows and direction, and form a block diagram of which junctions split out, and which combine signals.

There are multiple 4 junctions, but only one of these appears to combine signals.

Here is a block diagram showing the data flows between regions of the code patch represented as functions combining inputs, and showing a neat mapping of Rule110 inputs of

• L: Left cell
• C: Current cell
• R: Right cell
• N: Next cell

These 4 values MUST represent Rule110 boolean types (otherwise the program couldn't function).

The intermediate datatypes are not necessarily boolean, depending on what kind of signals Burn wires are able to carry. They could be integers, encoded in a variety of colours, some could be some kind of unary clock pulse which cannot be distinguished from a 0 or 1. I'm trying to not make any assumptions here, but figure out a minimum signal level that is required to make Rule110 work.

Flow / Block diagram of the Rule110 code based on the cell wires and numberings.

The block diagram shows there are 3 two-argument functions, and 1 three-argument function. (Unless I have made a mistake in dividing up the regions...)

Rule110 can be computed with the relatively simple boolean logic of:

def rule110(L, C, R):
   return (not (L & C & R)) & (C | R)

i.e.: Current OR Right, unless all cells are 1

There are similar variations.

A notable feature of this block diagram is that the full state of L,C,R is only transferred to the later stage of the program via the b1(a, b) function.

This converts the 3 LCR bits into two bits: (b1(L, C), b1(C, R))

Now, we kind of only need two bits to calculate next state N: (L&C&R, C|R), so this might be possible, but I haven't been able to find a way to extract that from the two results of a boolean b1(), which do appear to be the same function as that patch of code is reused across tile boundaries... (again: unless I'm looking at it wrong)

I also tried a lazy brute force random search for boolean function combinations, but didn't find anything that worked.

To prove that there is a solution that can fit these constraints, here are two solutions for making this Rule110 patch behave correctly with definitions of b1(), b2(), t1(), b3():

b1 = lambda a, b: a + b
b2 = lambda a, b: bool(a) | bool(b)   # bool(a) & bool(b) also works
t1 = lambda a, b, c: sum([a,b,c]) > 4
b3 = lambda a, b: bool(a) ^ bool(b)

With the solution framework provided by:

def rule110(L, C, R):
    A = b1(L, C)
    B = b1(C, R)
    D = b2(A, B)
    E = t1(A, D, B)
    N = b3(E, B)
    return int(N)

The 2nd solution involves b2() having the same overall effect with either a | b or a & b (it's a threshold rather than a boolean operator?) The bool()s are there to force values to bool types since in Python for integers: 5 & 2 == 0 , while bool(5) & bool(2) == 1

The common feature is that b1() adds its arguments, so its output is not just boolean. I don't know that Burn can't provide this ability, but I'd be happier if there was a boolean solution. Figuring out what constraints b1() imposes on the algorithm will likely provide some clues on what the Burn wires NEED to convey to make the code work.

I'm not completely happy with this solution, I'm going to pay more attention to types and see if there is a clever boolean trick to transfer all the information through the wires. The integer signal addition provides a lot of information, and the later stage looks more complex than it might need to be, but it needs further analysis.

Next steps are to figure out how Burn might transfer data along its wires and process them through the 'gates' given the block diagram. I think this shows there is enough room for the code patch to implement Rule110, and provides a skeleton for how it does so. Breaking up the 6x11 into functional patches with data flow constraints will hopefully help decode specific behaviours of the colours.