Emulate Rule 110 with Conway's Game of Life (or vice versa)

9

1

Can you find initial conditions for either Rule 110 or Conway's Game of Life to emulate the other? That is, produce output (in any form, not necessarily the familiar pixel grid) which corresponds directly to the other.

Rule 110 takes an infinite one-dimensional binary array as input, and outputs an infinite one-dimensional binary array using the values in the input array for the same position and the positions to the left and right, according to the following rules:

Input:   111    110    101    100    011    010    001    000
Output:   0      1      1      0      1      1      1      0


Example:

Conway's Game of Life takes an infinite two-dimensional binary matrix as input, and outputs an infinite two-dimensional binary matrix according to the following rules:

1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Example:

Challenges:

• How do you find initial conditions to match a specific output, when slightly different inputs produce vastly different outputs?
• How do you map infinite structures of different dimensions to each other?
• Do you have to throw away a lot of output to get the relevant bits from the other automaton?

Question was closed 2017-02-24T13:53:37.403

1@KSFT It's possible. a) The set of 2D integer coordinates is countable, so you can assign a single integer to each of them. b) Both Rule 110 and the Game of Life have been shown to be Turing complete, so you could just implement one of them in a Turing machine and then implement that Turing machine in the other. – Martin Ender – 2015-01-26T23:56:14.153

@MartinBüttner In theory, yes. Practically, that's nearly impossible. – Ypnypn – 2015-01-27T04:23:24.820

Since we can emulate Conway's Game of Life with Conway's Game of Life (http://www.conwaylife.com/wiki/OTCA_metapixel ), I think this is not so difficult.

– alephalpha – 2015-01-27T04:37:59.893

@Ypnypn Agreed. I don't see this getting answered any time soon, much like the Game of Life Tetris challenge. – Martin Ender – 2015-01-27T09:02:51.163

7