20 Nov
2003
20 Nov
'03
3:36 p.m.
der Mouse wrote:
To make another semi-random connection here, von Neumann was
very into the emergent behavior of simple automata known as
cellular automata. IIRC he was the first to prove that there
existed self-replicating CAs.
But is not
LIFE on the molecular level some thing like a bunch
computing machines that computes structure rather than logic.
Something like, maybe. But since chemical interactions involve
randomness randomness coming from the underlying quantum mechanics and
thus being, as far as we can tell, true randomness...nothing
deterministic is an accurate model. And that includes nondeterminstic Turing machines, as
I studied them,
since they don't pick one possible transition randomly but instead take
all possible transitions (which is why the power set construction works
to determinize such a machine).
Interestingly there does exist a model called a probabilistic automata
that operates in just that way. In fact, if you define what accept
means the right way for the model, it can be shown that there are
non-Turing
languages that can be accepted by a PA.
Brian L. Stuart