Mind-blowing geeky stuff

[spudtater]

I was thinking about Conway's Game of Life (look it up! now!) once again, thinking about patterns that generate infinite sequences of pattern, when I wondered: "is there a Conway pattern that will generate everything possible in the Conway universe? I thought of the Turing-completeness of the game of life, and the answer struck me.

Consider the following pseudo-code function, that generates all posible NxM arrays of bits when called with generator( 1, 1 ):

generator( integer N, integer M ):
    a = an N x M boolean array
    for x from 0 to 2 ^ ( N*M - 1 ) inclusive:
        y = x
        for i from 0 to N - 1 inclusive:
            for j from 0 to M - 1 inclusive:
                if y % ( 2 ^ (i*M+j) ) = 1:
                    a( i, j ) = true
                    y = y - 2 ^ (i*M+j)
                else:
                    a( i, j ) = false
        output a
    in parallel:
        generator( N + 1, M )
        generator( N, M + 1 )

Now, any language that is Turing complete should be able to implement this code. (There are hacks that allow you to do 'pseudo parallelism' by executing one statement of each process running in turn.)

Note that Conway's game of life is Turing complete. So this should be implementable in the game of life.

Conclusion: there exists some finite pattern of the game of life that will generate any given finite N x M pattern of the game of life after a finite period of time.

Additional, smaller, conclusion: there exist self-replicating patterns for the game of life.

Now we just have to find them!

(Edit: My flatmate Gary has just pointed out to me that this proof actually isn't true; the fact that the program can be implemented in the game of life only proves that some representation of every game of life pattern will be generated, not every life pattern itself. A very good point, but I leave my flawed proof here because it is intriguing nonetheless.)

This is mind-blowing! If the universe follows a finite and deterministic set of laws like the Game of Life does, and is Turing complete, then it is possible, but not neccessary that every possible finite structure will be created, every possible thought will occur to somebody, every possible book will be written, every possible LJ post posted, that Alex will exist in infinitely many variations infinitely many times. It all depends on the initial configuration. Does God exist? Was this his plan? Is this the true translation of "let there be light"? Or is he nonexistent? Or incompetent?

Under current models of the universe, it is unlikely that this is the case. For the universe to be Turing complete, it would seem to require infinite amounts of energy, matter and time, which doesn't appear to be true. Mind you, perhaps we could somehow create things smaller and smaller; entire worlds the size of the head of a pin, which would create smaller worlds, ad infinitum (N.B. each world would also have to operate at twice the speed of the last). Then it would be possible and we can rejoice in the prospect of infinite variety in all things. Or despair. 8^)

Comments

[martling.livejournal.com]

I would highly recommend you at this stage of thought to inspect:

• A Turing Machine implemented in Conway's Game of Life, one of the most beautiful things I have yet encountered and the necessary grounding for your initial assumption.
  
  
• Permutation City, by Greg Egan, which you will enjoy far more than my own commentary on your penultimate paragraph.

[spudtater.livejournal.com]

Thanks! I shall add that book to my list. To anyone interested in mathematical headfucks, I would also recommend the short story "The Library of Babylon" by Jorge Luis Borges. You can find it in many of the numerous collections of his stories.

Unfortunately, the turing machine doesn't seem to be in xlife file format, and I can't find one that is. Amazing nonetheless. Any ideas how large a universal Turing machine would be?