[Computation = Evolution + Observation?] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Computation = Evolution + Observation?

(Click here to view the original thread with full colors/images)


Posted by: martew

What is computation? This is a simple question, with a very hard answer. Maybe we can obtain "computation" just observing the "evolution" (the life) of some biological system.

In biology and chemistry a standard proceeding is to conduct an experiment, "observe" its progress, and then take the result of this "observation" as the final output. Therefore we do not need to construct new computing devices: we just take any biological system that "live" and we only need to observe such "life"! This combination (biological system + observer) will be our computing device!

Then, every biological system can become a computing device: we just need to find out the right observer!

What you think of this approach?

We wrote two papers on this topic where we have proven that such approach is very powerful (at least from a theoretical point of view). If you are interested you can find the papers in
http://www.geocities.com/matcav1975/papers
(I also attach here one of the two paper).

Thanks a lot for any comments, suggestions..
Best


Posted by: Jason Cawley

We can also compute just watching the progress-unfolding-evolution of non-living systems. Living systems, or non-living systems, can also perform computations that no one is watching. There is nothing fundamental to the notion, in either "living" or "observation". Those are additions, not requirements.

"I'd like to know what you think of such concept..is observation =
computation?"

I don't see why.

I read the paper on "Evolution and Observation". Now, in place of your membrame system put a physical instance of rule 110 or a universal Turing machine. Remove the observer from the system entirely. It is still universal. Next, case two, start again from your set up. Replace the membrame system with a simple look-up, a list of 1s and 0s, that just sits there and does nothing. Replace the observer with rule 110 or a universal Turing machine. Again it is universal - the string just sitting there is the input - initial conditions for 110, or tape for the TM.

Universality as a formal property of the computations of the entire system can reside in either part of it. If it is present in either part of it, then it is superfluous in the other part. Allowed, but not required. Moreover, the "join" or distinction between the two is entirely external to the question, what computations can this linked system perform? Which would arise in the same way, and be answered in the same way, if all of its components were parts of one finite-state machine and its rules.

There is no reason, incidentally, to select out behaviors that halt and regard them as "successful" computations. Behaviors that don't halt can also "count" as "successful" computations - they are just computations of something else. Moreover, there is no actual realizable "infinite hierarchy of behaviors" with additional objects. Once you have enough for universality, you've got all of it, everything a finite system can in principle do.

The complication of merely imagining one part of the system as biological, and of labeling one part of the system "observer", does not add anything fundamental. Finite state machines that are universal are easy to get. That is enough.

Now, the concept that your "observer" does correspond to in ordinary complexity and universality theorizing is that of an encoding or a translation between encodings. And there are interesting topics there. The main problem is to restrict what an encoding can do, to ensure that it is not supplying the universality one ascribes to the underlying system. In your terms, a universal "observer" can trivially "see" universal
computations in a static input (it takes them as its input "tape").

We require some notion of an encoding of a computation to ascribe some sense to statements like "system A can perform the same computations as B", when their underlying rules or components are not exactly equivalent. But this notion of encoding can't be so "wide" that we can "smuggle" universality into it, or we will ascribe universality to systems that do not in fact
possess it, simply because the encoder does possess it.

One approach to formulating such restrictions is requiring that any encoding or decoding takes very little time, in formal terms (that is, that the number of steps it must perform grows slowly with system size - number of elements etc). This is part of the general problem of formalizing what we mean by computational irreducibility, and so of computational reducibility. (Note that it is entirely possible for a universal system to behave in reducible ways, which thus can be "speeded up" or "short-cut". It is the
absence of any one system of speeding up, that works for anything the system can do, that marks "irreducibility").

I don't doubt that the way you set your picture of things up is intuitively useful for various biological systems, that you can imagine implimenting it with actual biological components, etc. That is fine. Just don't mistake staying close to your problem or your subject area, for a requirement of computation in general. Universal systems do not need a separate observer, and no component needs to be alive for any of it to be well defined.
Computation is an objective phenomenon, at bottom, something that happens in real relations.

Just showing simple membrane systems are universal is interesting in itself. The less need you have for a "sorting" observer, the stronger the result. In principle, I see no reason objects moved inside membranes could not perform all logic operations, or emulate Spencer-Brown forms (whose bracket structure might be mirrored in a hierarchy, for example), or some
other class of suitable formal systems known to contain universal instances.

Understand that getting to anything a finite system can do, with as little as possible, is the only interesting threshold. Transfinite issues are unimportant, as not physically realizable. Don't look for how much more you can add to get higher order infinities, look at how much you can take away and still get "computables". The action is all at the low end.

I hope this is useful, and I certainly encourage you to continue work on this stuff.




Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings