It's been proven that John Conway's "Game of Life" can function as a universal turing machine.
People have already put together life-configurations that model logic-gates, memory etc .
Would it not therefore be possible, to construct a compiler which takes somesort of machine-code (I would recommend a 'clone' of an old 8-bit processor like the 6502 would be a good start) and 'compiles' the end result to a 'Life-Grid' - ie) the end result would be a (huge?) initial Life-Configuration, which would run the program.
Things to thing about though:
1. The output from the compiler would need to output things like the memory store, ALU, data-busses etc etc as PART of the output.
[ This could be a separate exercise, and done only once I guess, thereafter we would could produce 'machine-code' that would work on a known-'processor'. ]
2. The computer would probably benefit from some 'external connections' - so that human-beings could actually read the output being generated from the program.-- monojohnny, Jun 06 2006 A smart Conway's Life Page. http://www.ibiblio.org/lifepatterns/http://www.ibiblio.org/lifepatterns/ [monojohnny, Jun 06 2006] Wikipedia: Rule 110 cellular automaton http://en.wikipedia..._cellular_automatonProven to be Turing-complete. [jutta, Jun 06 2006] 6552 VIA device for example http://en.wikipedia.org/wiki/6522http://en.wikipedia.org/wiki/6522 [monojohnny, Jun 06 2006] A Life Computer http://web.archive....ll.uk.co/gol/tm.htmNo longer on the web - but wayback machine found it. [monojohnny, Jun 07 2006] Golly life machine http://golly.sourceforge.net/The Golly life machine comes with some configurations that serve as bitmapped displays -- this seems a logical thing to use for the 6502's output device. Then... play Atari Combat! [regehr, Aug 30 2007] Wireworld Computer http://www.quinapalus.com/wi-index.htmlNot Conways Game of Life, but it is a computer implemented in cellular automata. [Bad Jim, May 31 2008] I've always thought that an array (2D or 3D) of really simple logic blocks (ie cellular automata) must be an efficient way of solving some problems (for example modelling an ideal gas represented by particles bouncing around in a box). It's just a matter of setting the rules correctly.
I think this concept is explored in Stephen Wolfram's "A New Kind of Science"
What types of problems were you thinking would be appropriate for this 'game of life' compiler?-- xaviergisz, Jun 06 2006 Wasn't thinking of any specific problem; however it would be interesting (more art than science?) to 'see' a machine-code program like this ( pseudo-code ):
LOAD REGISTER x,10 .loop DECREMENT X BY 1 BRANCH to '.loop' IF X==0
Running on a machine where you can actually SEE the working bits.....
It seems (as far as I am aware) that although very clever people have generated ad hoc programs using Life, wouldn't it open up a whole new opportunity for (simpler!) people to generate code using more standard mechanisms, and yet still still the results on the CA ?-- monojohnny, Jun 06 2006 [+] Not much of a step from this, to building hardware that maps the gates of learning and replicating algorithms... Hey presto - True Life!-- Dub, Jun 06 2006 You could nail a whole bunch of turing-complete systems and just translate the assembler into e.g. cyclic tag system operations. Just don't expect the results to make sense to a human observer.-- jutta, Jun 06 2006 I think it be nice to extend the life-grid - give it an "interface" to a another program which would take (say) a stream of gliders and translate into binary->whatever you want.
Kind of like the equivalent to a 6522 VIA device that was used to talk to external stuff.
Maybe we start of with a simple ASCII VT100-style terminal.
Of course this part would be completely outside of the CA, and would only function to prove the programs were running as expected....
(link added for 6522)-- monojohnny, Jun 06 2006 Someone did do a wireworld computer (see link). The site also claims a Turing Machine was implemented in Life.
This kind of thing is a glorious waste of time so I won't bun it. But I won't fishbone it either, because it's the kind of thing I get up to and it can be educational.-- Bad Jim, May 31 2008 Output to molecules of DNA: Create a god!-- Voice, Jun 03 2008 random, halfbakery