ijp@doc.ic.ac.uk (I J Palmer) (05/09/91)
I sort of lost contact with this news group (Easter and all that) and so
don't know how the 'Winning Ways ...' thing ended, but (not wishing to bring
back the dead) something struck me as I was sitting there (as one does)
and that is this ...
Conway states that Life is `Universal' in that you give him a problem, and
he can construct a Life thingy to solve it (if it is solvable). But, I say,
what about getting Life to find (at this point I'd like to point out the
nice allignment of Life (the word) in this paragraph) a `Garden of Eden' or
Orphan (pad pad..) Life pattern. This is, I think, a computable problem
which, by definition, Life (it had to stop somewhere) can not solve !!!!
Or perhapse I'm thick, but if this is the case where does my logic (eek)
fall down ?????
I appologise in advance for my signature...
_____
/_ _/ Let Total Chaos reign forever ! I.J.Palmer,
/ / ___ ______________ Department of Computing,
/ / / __\ | _ Imperial College,
/_/ / / | <> | /-\ |_ 180 Queen's Gate,
\ \__ / _ London SW7 2BZ.
\___/ \ |-| /-\ <> <
______________> ijp@doc.ic.ac.uk
PANIC NOW
and avoid 23. Add to Celt's pub meal and produce utter turmoil. (6,8)
the rush. -----------------------------------------------------------chappell@antares (Glenn Chappell) (05/09/91)
In article <1991May8.203654.7838@doc.ic.ac.uk> ijp@doc.ic.ac.uk (I J Palmer) writes: >Conway states that Life is `Universal' in that you give him a problem, and >he can construct a Life thingy to solve it (if it is solvable). But, I say, >what about getting Life to find (at this point I'd like to point out the >nice allignment of Life (the word) in this paragraph) a `Garden of Eden' or >Orphan (pad pad..) Life pattern. This is, I think, a computable problem >which, by definition, Life (it had to stop somewhere) can not solve !!!! Well, yes, Life *is* Universal, and it can *find* the solution to any solvable problem, but it may not be able to communicate this solution to you in a "nice" way. As an analogy, suppose I have some sort of language which doesn't have the word "Eden" in it. With the language I can solve any problem. What if the answer to the problem is "Eden"? It might be expressed this way: The first letter is "E" The second letter is "d" The third letter is "e" The fourth letter is "n". Similarly, some sort of Life computer might be able to find a Garden of Eden pattern, and "tell you what it is" without that pattern ever actually existing within the automaton. GGC <><
callahan@cs.jhu.edu (Paul Callahan) (05/09/91)
In article <1991May8.203654.7838@doc.ic.ac.uk> ijp@doc.ic.ac.uk (I J Palmer) writes: > But, I say, >what about getting Life to find (at this point I'd like to point out the >nice allignment of Life (the word) in this paragraph) a `Garden of Eden' or >Orphan (pad pad..) Life pattern. This is, I think, a computable problem >which, by definition, Life (it had to stop somewhere) can not solve !!!! > >Or perhapse I'm thick, but if this is the case where does my logic (eek) >fall down ????? Not a bad try, but here's where it fails. Life can simulate itself at a level more amenable to this kind of meta-reasoning than the actual life grid. For example, one could probably construct big life patterns fitting in, say, 1000x1000 squares, such that when these patterns are packed into a grid in the normal way, the resulting interactions simulate a Life grid (i.e., each pattern acts as a cell in a cell-automaton with data stored according to a fixed encoding scheme using glider interactions for computation, and this cell-automaton happens to obey the same rules as Life). If you believe that Life can simulate itself in this manner (there are lots of other ways, of course), it is not hard to imagine introducing extra controls in the simulation (for example, allowing the setting and resetting of a arbitrary cells) which would make it possible to construct any Life pattern for testing purposes, *including* those that no parent can give rise to. In other words, Life can simulate a computer which simulates Life, but allows some extra tinkering not specified by the Life rules. This should allow it to reason about the existence of Garden of Eden patterns. Obviously, there's more to it than this, but my point is simply that the inability of a Life pattern to construct an "actual" Garden of Eden pattern does not imply an inability to construct a simulation of a Garden of Eden pattern, which is all that people can do, after all. -- Paul Callahan callahan@cs.jhu.edu