Sasha ([info]alexanderwait) wrote,
@ 2004-09-12 10:20:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
Live from ALife IX...
I am listening to an interesting talk about a computational model of DNA computing-- at the ALife IX conference-- this morning. My talk An Evolutionary Approach Generates Human Competitive Corewar programs seems to have gone OK. I was the first speaker at the Artificial Chemistry workshop. In a few minutes I'll be having lunch with my old adviser--Gilles Brassard-- who is flying to boston just to hear my tutorial this afternoon. If you are interested, please, sign up to my low traffic mailing list.

I also have a poster here. Have a look:

(10 comments) - (Post a new comment)


[info]shamebear
2004-10-21 09:53 am UTC (link)
Hi! I'm not familiar with coreworld or corewar, but know tierra and some other alife programs. If I had stumbled into this conference, the first question I'd ask after seeing your poster would have been "are three spatial dimensions necessary for this to work", whereupon I'd point at the figure in the middle.
We know from Conways game of life and Wolframs cellular automata that a turing machine is possible for 2D and 1D cellular automata. Also, far as I gather, displaying the organisms in Tierra in a 2D plane is purely for simplification, all "points" are lines in code, itself a 1D string of bits.
However, it has been argued that biological life as we know it could not arise in anything but a 3D world, due to demands from physics on gravity and stellar nuclear reactions.

What's your opinion on demands for spatial dimensions? Can they be exchanged for other degrees of freedom like diversity in the assembler-code and number of bits in a byte, or are spatial dimensions unique degrees of freedom that can't be done without in alife?

(Reply to this) (Thread)

[info]alexanderwait
2004-11-07 10:07 pm UTC (link)
"are three spatial dimensions necessary for this to work" -- I have no idea but -- my intuition says "yes". Let's see what happens!

(Reply to this) (Parent)(Thread)
Rule 110
[info]ciranox
2004-12-21 06:40 am UTC (link)
Ok here's an even easier way to answer the question. You could probably push out a paper on the topic.

I hate Wolfram. He's egotistical and incapable of writing cogently.

Despite this, take Wolfram's Rule 110, which is known to be universal. Now find a way to obtain Rule 110 on a CA with a 3 dimensional graph topology. The easiest way to look at this is as follows: The 3D cellular automaton can still be displayed on your computer screen as a 2 dimensional set of notes. Except that the connections between the nodes are now nonlocal in some way. But if you see the same Rule 110 patterns emerge on this set of nodes as would occur on the locally connected planar set, then you've got it! This might be surprisingly easy, might take only a week to do.

(Reply to this) (Parent)(Thread)
Re: Rule 110
[info]alexanderwait
2004-12-27 04:16 pm UTC (link)
"The 3D cellular automaton can still be displayed on your computer screen as a 2 dimensional set of notes."

I'm using a 3D Euclidean space precisely because we can visualize it with off-the-shelf 3D graphics toolkits. Analysis of these evolving, artificial worlds is hard. I think it's helpful to have tools that are convenient (for humans).

(Reply to this) (Parent)
Dimensionality and universality
[info]ciranox
2004-12-21 06:34 am UTC (link)
We know from investigations of graph theoretical nature that an N dimensional graph topology (which would be necessary, say, to achieve the equivalent of a 3 dimensional cellular automaton) are obtained simply by altering the locality of the connections between nodes.

If you want to create a "3 dimensional" cellular automaton you simply alter the connections between cells in such a way that the graph of nodes representing the automaton (in which each node is a finite state machine, etc etc) is no longer a planar graph.

The question you are asking boils down to this: given a cellular automaton with a nonplanar graph of connections, does there exist a planar graph that can perform the same computation? YOu then have to examine how the state machine of each node would be modified by the change of topology.

My intuition says, yes it is possible for a class of 3D automatons, but not for all of them. Proving the universality of one of the members of this class will answer your question. If we are to believe Wolfram's computational equivalence conjecture, then it is very likely you will find such a computationally universal member in the set of 3D CA's that can be emulated by 2D ca's. Ok?

So get to work!!

(Reply to this) (Parent)(Thread)
Re: Dimensionality and universality
[info]alexanderwait
2004-12-21 07:38 am UTC (link)
The Quantum Coreworld ecology has: local structure (3D), quantum information processing (of classically simulatable states), a flow and (re)cycling of "nutrients", (limited) interactions between coreworlds. Quantum Computers have no special capabilities in a "computability" sense and a 2D CA or a 1D Turing machine can certainly simulate the Quantum Coreworld. What we really want, however, is a theory that lets us predict what sort of "lifeforms" might emerge in the Quantum Coreworld as a function of the passage of time for an ecology of a given size. If 2D versus 3D means that "interesting" lifeforms emerge asymptotically sooner, that would be a nice contribution to the understanding of evolution. (Same thing for Quantum versus no Quantum or lifeforms without "metabolism".) IMHO "Wolfram's computational equivalence conjecture" - like computability theory - is too general to answer the questions we want answered.

(Reply to this) (Parent)(Thread)
Re: Dimensionality and universality
[info]shamebear
2004-12-26 12:14 am UTC (link)
I agree that Wolfram isn't much help here. I must also admit to know too little about graphs resembling euclidean spaces to make use of that approach.

However I liked the approach taken by for instance Kauffman in his book "at home in the universe" Consider a grid of "lightbulbs" where the input to each lightbulb is the state of the other lightbulbs it is connected to. Each set of inputs produce either light on or light off as output. Kauffman shows the "interesting" range to be at the "edge of chaos" for certain settings. A setting of K = 2 connections to other lightbulbs appear good. If K is increased, another parameter P should be adjusted to compensate.

P can be defined as (Number of input-combinations that give ON as output)/(Total number of input-combinations) and is a measure of the bias the lightbulb has towards one setting. If this bias is strong (P near 0 or near 1), the network may still be in the interesting range if K is high.

In a 2D cellular automata, each cell usually have four neighbours. in 3D it has six. That means our "lightbulb" should show a strong bias to compensate. (Kauffman also advices to stick to so-called "canalyzing" boolean functions)

These seem like good practical advices. While Kauffman talks of abstract spaces, not real-life euclidean, that's not too bad! Kauffman claims that life started as an "autocatalytic process", a certain web of chemical reactions in the primordial soup. Each cell then get to symbolise a certain molecule and the flow of nutrients could symbolise the relative amounts of molecules as one is spent to produce another. When it's all jumbled in a soup anyway, the elements exact position in the bowl is secondary.

"interesting" behaviour could be several instances of the same nearly closed webs of reactions (different individuals of the same species), showing homeostasis yet never stopping their evolution.

If these webs could be identified and displayed properly, very interesting behaviour would be allowed to occur on the screen without basing it in a physical space.

(Reply to this) (Parent)(Thread)
Re: Dimensionality and universality
[info]alexanderwait
2004-12-27 03:59 pm UTC (link)
"While Kauffman talks of abstract spaces, not real-life euclidean, that's not too bad! Kauffman claims that life started as an "autocatalytic process", a certain web of chemical reactions in the primordial soup. Each cell then get to symbolise a certain molecule and the flow of nutrients could symbolise the relative amounts of molecules as one is spent to produce another. When it's all jumbled in a soup anyway, the elements exact position in the bowl is secondary."

There have been lots of attempts to build evolving, artificial worlds with "a certain web of chemical reactions." But these webs are very hard to analyze. It's much simpler, frankly, to use 3D euclidian space.

(Reply to this) (Parent)
Re: Dimensionality and universality
[info]ciranox
2004-12-27 03:34 pm UTC (link)
Yes, if you solve the question of predicting lifeforms in the quantum coreworld, which is by the way a very great idea -- the notion of core organisms on a 1D turing machine is the most basic way to represent the idea of darwinian evolution of organisms in a nonstochastic algorithmic-state-machine framework -- if you solve the question of prediction, then you've also solved the question of complexity in general, and you may go and collect your nobel prize!

Comparing a classical versus a quantum coreworld gives rise to the -- perhaps impossible -- question, is it possible that our universe is in fact a quantum turing machine?

Where does quantum randomness arise from? It seems that at the fundamental level the universe might be equivalent to a turing machine with a perfectly-random number generator built into its instruction set. It is impossible to predict when a particle decay will occur...this is indicative that at a very fundamental level, the universe is constructed upon a background of randomness.

If you put a bucket of ball bearings on a paint-shaker, the otherwise disordered movements of the bearings will give rise to wave-like entities on the surface, they appear like gaussian spikes, and they move around and interact. Perhaps the universe is like this.

The notion of a quantum coreworld is intruiging because as I see it, this is a bridge between two realms that we cannot reconcile right now. On the one hand, the only coreworlds we have available to us right now are classical deterministic algorithmic state machines. We can create darwinian evolution in them, but they are a different realm than the reality upon which we have evolved, in that our reality at a fundamental level has randomness built-into it and therefore cannot be simulated on a classical algorithmic state machine.

On the other hand, someday we will have true quantum computers. If you create a quantum computer and then create a coreworld on this computer you've got it! It will be a grand experiment in emergence! If you begin with the correct ruleset for the turing machine, you will probably get entities that ca be classified as 'organisms' but which, from the proper viewpoint, are an analog of particles, atoms and other building blocks for instance! It is conceivable that a coreworld on a quantum turing machine running the correct set of instructions will give rise to a universe identical to ours.

Protons are merely turing-organisms, a stable population in memory.

(Reply to this) (Parent)(Thread)
Re: Dimensionality and universality
[info]alexanderwait
2004-12-27 04:11 pm UTC (link)
"...if you solve the question of prediction, then you've also solved the question of complexity in general..."

Before tackling a "general" prediction problem, my goal is to make predictions about interesting special cases. The Quantum Coreworld is designed to make it easy to do that. It's a digital evolution laboratory.

"Comparing a classical versus a quantum coreworld gives rise to the -- perhaps impossible -- question, is it possible that our universe is in fact a quantum turing machine?"
I'm interested in the more specific questions: Is our biosphere quantum mechanical in an interesting way? What experiments, if any, could distinguish quantum lifeforms from classical lifeforms?
"On the other hand, someday we will have true quantum computers. If you create a quantum computer and then create a coreworld on this computer you've got it! It will be a grand experiment in emergence! If you begin with the correct ruleset for the turing machine, you will probably get entities that ca be classified as 'organisms' but which, from the proper viewpoint, are an analog of particles, atoms and other building blocks for instance! It is conceivable that a coreworld on a quantum turing machine running the correct set of instructions will give rise to a universe identical to ours."
For my PHD I've gone out of my way to emphasize that we don't need a real quantum computer to see a selective advantage for quantum information processing. In fact, we can simulate many aspects of quantum information processing faithfully on a classical computer. (I know that seems strange but it's true.) I'm trying to finish an essay about this in the next few days; I'll post about it again soon.

(Reply to this) (Parent)

(10 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…