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:
- Any live cell with fewer than two live neighbours dies, as if caused by under-population.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overcrowding.
- 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?
l0b0
Posted 2015-01-26T23:17:27.617
Reputation: 191
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
Here is an answer by Jason Summers in 2005: http://pentadecathlon.com/lifeNews/2005/12/rule_110_unit_cell.html
– alephalpha – 2015-01-27T11:58:27.6631I know this question is old and rules have changed, but I am voting to close this as off-topic, because as it stands the [popularity-contest] requires some goal for humans to arbitrate over, and this provides none. Interesting challenge but it needs a criterion. – Post Rock Garf Hunter – 2017-02-24T05:18:55.400