Functional Programming In Life

That's "Life" as in GameOfLife

It's well known that one may build a TuringMachine within the GameOfLife. But could one simulate other models of computation within it?

If one did, would that be an example of NonTuringComputation??

Functional Programming

Technical issues:

A lot of computationally useful starting patters for Life are iterative and contain fixed structures and/or glider guns and such, to clean up the side-effects of each step in an iteration.

It would be interesting to see generic GarbageCollection in the GameOfLife, as this would probably be required for a working FP system. But not certainly required. For example, the ML kit compiler for MlLanguage does something called region analysis and can so statically determine the lifetime of every object. It doesn't need pointer-tracing GarbageCollection.

Apparently, this relies heavily on ML's strong static type system. Sometimes objects can be released that are still reachable (and which would thus be considered "life" by a conventional GC), but which are provable irrelevant to future computations. All this seems extremely cool. -- StephanHouben and KeithBraithwaite

For more info, see http://www.it-c.dk/research/mlkit/kit3/readme.html

Then again, maybe it wouldn't matter. We can't really build TuringMachines at all, since we can't provide an infinite tape, but we can fake it up as well as is required for practical purposes. Similarly, our Life FP system could perhaps be run in an "infinite enough" space that GC didn't become an issue.

I was under the impression that the TuringMachine-in-Life requires an infinite space to run in. So we can also assume an infinite amount of space when implementing out FP system, in which case we don't need any GarbageCollection at all.

-- StephanHouben

Paul Rendell's Turing Machine in Life: http://rendell-attic.org/gol/tm.htm