Principle of computational equivalence

[UndercoverElephant]

I mentioned this in Robin's poll, but nobody responded.

http://en.wikipedia.org/wiki/A_New_Kind_of_Science


A New Kind of Science (NKS) is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata. Wolfram calls these systems simple programs and argues that the scientific philosophy and methods appropriate for the study of simple programs are relevant to other fields of science.


This is the key claim of the book:


Principle of computational equivalence

The principle states that systems found in the natural world can perform computations up to a maximal ("universal") level of computational power. Most systems can attain this level. Systems, in principle, compute the same things as a computer. Computation is therefore simply a question of translating inputs and outputs from one system to another. Consequently, most systems are computationally equivalent. Proposed examples of such systems are the workings of the human brain and the evolution of weather systems.


An example of what this means:

Problem: How do you create a living system like the Earth's ecosystem? Can it be designed by an intelligent entity?

Answer: The only system capable of performing that calculation is the natural world itself. There is no more efficient way to perform the calculation. You'd need a computer more complex than the natural world itself to perform the computations required to arrive at the solution externally.

?

[rocketdodger]

An example of what this means:

Problem: How do you create a living system like the Earth's ecosystem? Can it be designed by an intelligent entity?

Answer: The only system capable of performing that calculation is the natural world itself. There is no more efficient way to perform the calculation. You'd need a computer more complex than the natural world itself to perform the computations required to arrive at the solution externally.

?

That does not follow, because you are only considering the final state of the system.

If you include all of the iterations it took natural selection to end up with some pretty obvious solutions, then the natural world starts to look pretty inefficient indeed.

And, I think you misunderstand the gist of the article. I think the point is that computation is a pretty universal process that occurs in all sorts of systems, and pretty big subset of those can be viewed as turing equivalent.

[temporalillusion]

That does not follow, because you are only considering the final state of the system.

If you include all of the iterations it took natural selection to end up with some pretty obvious solutions, then the natural world starts to look pretty inefficient indeed.

And, I think you misunderstand the gist of the article. I think the point is that computation is a pretty universal process that occurs in all sorts of systems, and pretty big subset of those can be viewed as turing equivalent.

Yeah, I'm not sure that Problem/Answer is a good example of what it's talking about, the Answer doesn't even seem to address the question.

This is the way I would understand it:

Problem: How do you compute the future state of a system like the Earth's weather?

Answer: The only system capable of performing that calculation is the Earth itself. There is no more efficient way to perform the calculation. You'd need a computer more complex than the Earth itself to perform the computations required to arrive at the solution externally.

Meaning that if we wanted to perfectly compute what some future state of the Earth's weather would be, we'd have to perfectly compute the state of every atom, molecule, photon, etc.. And the most efficient way to do that is to actually have the atom, molecule, photon flying around doing their thing. To compute it externally would require a computer more complicated than the Earth itself.

Of course with current weather modeling or whatever we get around this limitation by using models, which approximate things, so we can get an approximate of the future state without having to compute every detail. If all we want is if it's going to rain a model might be good enough, but it's not going to give us the exact state of every atom and photon.

EDIT: Sorry, didn't read the other thread yet.

Hm.. with respect to evolution vs. intelligent design, wouldn't it just be saying that the simplest way to compute a living ecosystem is by the ecosystem itself? The principle doesn't say it's impossible for something else to compute it, just that whatever does will be more complex. Which is no problem because God is infinitely complex! ;)

[UndercoverElephant]

deleted

[UndercoverElephant]

That does not follow, because you are only considering the final state of the system.

If you include all of the iterations it took natural selection to end up with some pretty obvious solutions, then the natural world starts to look pretty inefficient indeed.


OK. Let's get this clear. You think that ID, via Occam's razor, is a simpler solution than naturalistic evolution?

[rocketdodger]

OK. Let's get this clear. You think that ID, via Occam's razor, is a simpler solution than naturalistic evolution?

If you ignore the designer, absolutely.

How can there be any doubt? By all reasonable accounts it has taken natural selection hundreds of millions of years to get to us. If we started fresh, right now, we could do the same in probably a hundred.

You would have to be pretty stupid to "ignore the designer," though.

[Dancing David]

I mentioned this in Robin's poll, but nobody responded.

http://en.wikipedia.org/wiki/A_New_Kind_of_Science



This is the key claim of the book:



An example of what this means:

Problem: How do you create a living system like the Earth's ecosystem? Can it be designed by an intelligent entity?

Answer: The only system capable of performing that calculation is the natural world itself. There is no more efficient way to perform the calculation. You'd need a computer more complex than the natural world itself to perform the computations required to arrive at the solution externally.

?

When you say like do you mean 'exactly' like or 'similar' like. Yes to mdeol the earth's ecosystem as a whole would be daunting. To model a small portion of it (a very small portion) would be easier.

But there would be a problem in trying to model the whole system of the earth in a finite detail scale that say involved all amino acid bases. If you used algorithmic approximation at higher scales, you might come up with an approximation, but then it would run very slowly at any rate.

[Dancing David]

OK. Let's get this clear. You think that ID, via Occam's razor, is a simpler solution than naturalistic evolution?

I disagree with RD on this one, no.

They are equal in many ways, the issue would be what difference would it make.

I would hope that an intelligent designer would not have so many strange parts to the design. (unless itw as justa fashion statement.)

I mean really why hair on my face, really?

[rocketdodger]

I disagree with RD on this one, no.

They are equal in many ways, the issue would be what difference would it make.

I would hope that an intelligent designer would not have so many strange parts to the design. (unless itw as justa fashion statement.)

I mean really why hair on my face, really?

But I am not talking about the complexity of the design itself, I am talking about the complexity of the process of designing.

I can program some AI to arrive at a solution to some problem in an elegant way using an algorithm with a minimum number of steps. Solving the same type of problem using something like a learning or genetic algorithm would involve much more complexity.

Granted, the solution might be equivalent once found.

[Myriad]

Computational Equivalence (as Wolfram posits it) does not mean that all methods of computing something are equally efficient. Only that any computation that can be performed by one computationally universal system can also, in principle and given arbitrary amounts of time, be performed by any other. However, one or the other may take a vastly greater number of steps to perform that computation.

This was known in computing theory long before Wolfram. Wolfram's contribution is to greatly expand the variety of systems that are known to be computationally universal, and to hypothesize (with a strong argument but no proof yet) that the actual variety of systems that are computationally universal is even greater still, encompassing more or less every system that operates on a set of rules and exhibits behavior that goes beyond trivially simple.

So, the PoCE doesn't declare it impossible that some other computer could compute earth's future weather faster than earth itself does. But it does claim that the other computer would have to do it in basically the same way: start with the starting state and compute the evolution of the system step by step. There's no shortcut where you can just, for instance, take some weather equation (however complex) and put in a value for elapsed time t and calculate the result directly, the way you can determine the orbital position of a body in a Newtonian two-body system at any arbitrary future time just by plugging the staring conditions and time into an equation.

What the PoCE really means is that for most or all complex phenomena in nature, the behavior cannot be described or predicted by straightforward equations, because they are universal computers themselves. Therefore their behavior can only be known by either allowing them to run, or by simulating them with other universal computers and allowing those to run.

For instance, consider a Newtonian system with three bodies. No general equation describing the future configuration of such systems as a function of their starting configuration and elapsed time has been discovered, and the behaviors that such systems can exhibit are quite complex. If the Principle is correct, that complexity of behavior means three-body systems are computationally universal. That means in principle you could design the starting configuration for a three-body system to "program" any conceivable computation. But it also means that finding an equation that tells you the future configuration of any three-body system, just by plugging in the starting configuration and elapsed time (the way you can for a two-body system), is impossible. If there were such an equation, you could apply it to any three-body system programmed for any computation whatsoever. You'd be able to do any possible computation in a few steps. It would be like being able to scan any computer program and figure out what its output would be, without actually running the program. That has already been proven to be impossible (again, prior to Wolfram).

One interesting open question for Wolfram's PoCE is whether quantum computers turn out to be capable of shortcutting computation or not, by operating on a superposition of multiple steps of the problem simultaneously. If they work well, for instance being able to factor a huge number in a short time, then the Principle will be falsified. If they turn out to have practical limitations (such as, perhaps, that when properly set up to give the result of a complex problem like factoring a huge number in one step, they take so long to collapse into a result state that the same computation could have been done faster by other means), then the Principle will stand. Either way, we'll have some additional insight into how the universe works.

Respectfully,
Myriad

[temporalillusion]

Thanks for the informative post Myriad!

Would a quantum computer really falsify the Principle though? Just because the steps are being evaluated simultaneously? Wouldn't that be similar to what you said about a computing the earth's weather faster than the earth does? Rather wouldn't the same # of steps have been taken, they just happened to be all taken at the same time.

The complexity of the computer still comes into play; I would still need more bits (or however such things are measured formally) than the original wouldn't I?

[UndercoverElephant]

If you ignore the designer, absolutely.

How can there be any doubt? By all reasonable accounts it has taken natural selection hundreds of millions of years to get to us. If we started fresh, right now, we could do the same in probably a hundred.

I don't agree. I think you'd end up having to do an almost infinite number of calculations in order to make sure the whole thing fitted together properly. I strongly suspect that the natural world itself is the most efficient way of "computing" the solution to the problem "how do you make a living ecosystem."

[HansMustermann]

That does not follow, because you are only considering the final state of the system.

If you include all of the iterations it took natural selection to end up with some pretty obvious solutions, then the natural world starts to look pretty inefficient indeed.

And, I think you misunderstand the gist of the article. I think the point is that computation is a pretty universal process that occurs in all sorts of systems, and pretty big subset of those can be viewed as turing equivalent.

Hmm, I see nothing there that would suggest looking only at the end result. If anything, IMHO your second paragraph looks like that.

Way I understand that equivalence, it's more about doing the same thing, than about arriving at the same end result via a different way. _If_ such a computer/finite-automata/etc model is indeed equivalent to Earth's eco-system, it would react in the same way to the same changes in its inputs (e.g., climate changes, volcanic erruptions, snowball Earth catastrophe, big freaking meteor hit, etc). So given the same historical sequence of those inputs, an equivalent system would necessarily go through the same steps as the real world did.

[HansMustermann]

If you ignore the designer, absolutely.

How can there be any doubt? By all reasonable accounts it has taken natural selection hundreds of millions of years to get to us. If we started fresh, right now, we could do the same in probably a hundred.

You would have to be pretty stupid to "ignore the designer," though.

Well, maybe if we had better tools and better programmers.

I mean, seriously, the whole genetic code for a human (including the data segments, i.e., junk DNA) is about 750 MB, or about a CD. That is not just for the AI, but also for the whole metabolism, enzymes, immune system, self-regulation, self-repair, cell specialization, etc, etc, etc.

Do you think we could program a better one if we started from scratch today?

I doubt it. We're not even close to making the learning AI part yet. (Seems like we're finally going somewhere after turning to a more bayesian approach, though.)

Design a better metabolism and generally biology to go with that AI? Heh. The best we can do right now is basically copy existing genes -- those that _nature_ has created -- from one life form to another. We're barely at a stage equivalent to the burger-flipper copying and pasting functions from one program to another, without really fully understanding them. We're _not_ at a stage where we can even code one protein from scratch.

And do it all in 750 MB? Heh. Nowadays we can barely manage to fit one spreadsheet in that space. Your average project nowadays has more than that just in cute widgets, abstraction layers, and libraries included just because the programmer wanted that buzzword on the resume. If we designed a human nowadays, I bet it would include needlessly transforming every signal into XML and parsing it back from XML, just because someone thought it's cool.

So, well, no we couldn't even make a whole life form from scratch yet, much less a whole planet-wide ecosystem :p

[Dancing David]

But I am not talking about the complexity of the design itself, I am talking about the complexity of the process of designing.

I can program some AI to arrive at a solution to some problem in an elegant way using an algorithm with a minimum number of steps. Solving the same type of problem using something like a learning or genetic algorithm would involve much more complexity.

Granted, the solution might be equivalent once found.

Fair enough.

[rocketdodger]

So, well, no we couldn't even make a whole life form from scratch yet, much less a whole planet-wide ecosystem :p

I said "within 100 years," and I only use that estimate assuming that something like the singularity will occur within 50. So... that is alot of possibility.

[rocketdodger]

Hmm, I see nothing there that would suggest looking only at the end result. If anything, IMHO your second paragraph looks like that.

Way I understand that equivalence, it's more about doing the same thing, than about arriving at the same end result via a different way. _If_ such a computer/finite-automata/etc model is indeed equivalent to Earth's eco-system, it would react in the same way to the same changes in its inputs (e.g., climate changes, volcanic erruptions, snowball Earth catastrophe, big freaking meteor hit, etc). So given the same historical sequence of those inputs, an equivalent system would necessarily go through the same steps as the real world did.

Yes, that is correct.

But I think that UCE is still talking about only the final result, regardless of how one arrives at it.

[Myriad]

Thanks for the informative post Myriad!

Would a quantum computer really falsify the Principle though? Just because the steps are being evaluated simultaneously? Wouldn't that be similar to what you said about a computing the earth's weather faster than the earth does? Rather wouldn't the same # of steps have been taken, they just happened to be all taken at the same time.

The complexity of the computer still comes into play; I would still need more bits (or however such things are measured formally) than the original wouldn't I?


That's apparently not an easy question to answer in the current state of NKS. Here are Wolfram's notes on Quantum Computers: http://www.wolframscience.com/nksonline/page-1147d-text?firstview=1. Basically, he doesn't think quantum computing processes are any more efficient for NP-complete problems once you include the computations necessary to set up the inputs and extract the outputs from the quantum computer. With some possible exceptions such as factoring. (And he notes that factoring has not been proven NP-complete.)

Others' commentary that I've read on the question is somewhat divided. There seems to be general agreement (but I wouldn't quite call it consensus) that successful quantum computing would at least weaken the PoCE. That's because the PoCE is partly rooted in computing theory, and in computing theory a big deal is made of whether or not a computation takes exponential time or polynomial time as a function of the size of the problem (e.g. the number of digits in the number to factor). Even a grossly inefficient polynomial time algorithm (e.g. one having large exponents such as time increasing as the sixth power of the size of the input) is considered fundamentally different, and in some basic sense "more computable," than even an efficient exponential time algorithm (e.g. one having a function like time increasing as 1.01 raised to the power of the size of the input). In principle, the latter will always exceed the computing time of the former if the input size is big enough. (In practical computing the latter would likely be faster, depending on the specific problem at hand, but computing theory is more about general principles.) Quantum computing would have to break down that barrier in order to live up to the more optimistic predictions for it. (A more limited success would be providing faster computation of certain non-NP-complete problems. Merely functioning with the same capabilities as a regular computer would not be much of a success at all, though it might still be useful for the study of quantum mechanics.)

I should have made it clear that the idea that successful quantum computing would falsify the PoCE is my own interpretation which others would disagree with. One of the problems is that there is no concise statement of the PoCE to work from.

Respectfully,
Myriad

[rocketdodger]

I don't agree. I think you'd end up having to do an almost infinite number of calculations in order to make sure the whole thing fitted together properly. I strongly suspect that the natural world itself is the most efficient way of "computing" the solution to the problem "how do you make a living ecosystem."

Well, there are mathematical ways (we do it in computer science all the time) to estimate how long a given problem solving approach can take. Typically, using the kinds of heuristics and memory that the natural world does not have access to results in much faster calculations.

At the very least, an intelligent entity has a memory of what approaches failed in the past, and can totally bypass trying them when faced with new problems of a similar type. Not so with nature -- for example, we observe that evolution has come up with multiple independent solutions to many problems, and that is wasted computation if a single solution works across the board.

Furthermore our memory allows us to use heuristics to jump straight to likely solution candidates, or at least cull a huge number of possible solutions without spending much time considering them. Again, nature doesn't do this -- a bad mutation that results in a sterile creature isn't realized until the creature attempts to mate and fails to bear offspring. An intelligence, on the other hand, could look directly at the mutation as soon as it occurs and (if smart enough) realize it just won't work at all.

[HansMustermann]

I said "within 100 years," and I only use that estimate assuming that something like the singularity will occur within 50. So... that is alot of possibility.

Ahhh... the "a miracle happens here" kind of plan. I like those :p

[temporalillusion]

I should have made it clear that the idea that successful quantum computing would falsify the PoCE is my own interpretation which others would disagree with. One of the problems is that there is no concise statement of the PoCE to work from.

Respectfully,
Myriad

Cool, thanks again for the informative post and the link, interesting stuff.