A New Kind of Science: The NKS Forum - Why Does Universality Matter?

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0

A New Kind of Science: The NKS Forum > NKS Way of Thinking > Why Does Universality Matter?

Last Thread Next Thread

Author

Thread

aiprof01

Registered: May 2006
Posts: 12

Why Does Universality Matter?

The fact that some automata are universal that are nevertheless composed of a small set of simple rules is often brought up as a compelling argument for NKS.

Yet what I am wondering is what practical consequence such universality has towards real computation?

In practice, what really matters in computation is getting the system to perform the computation that you actually want. If that computation is within whatever set of procedures that are possible to compute by some system, then it makes no practical difference whether the system is universal or not.

The real issue is whether it is easy to discover (which may mean through analytic construction or through search) the particular computational system that you want. Given a particular encoding (such as a CA) it may or may not be easy to make such a discovery.

Yet the important issue is that it may be _easier_ to discover what you want in a paradigm that is NOT universal. Thus universaility and tractability are orthogonal; what matters much more than the universality, which is just a theoretical curiosity, is the ability to do what you want.

Now, you might argue that to be sure you can do what you want you need universaility. However, that argument is well known to be naive. A machine that can do anything may in practice do nothing at all because its parameters exist in such a vast search space. It's really the nature of the search space that is interesting for any practical application.

It is a common phenomenon in AI that someone demonstrates a complete system and then its performance is crushed by an incomplete one that is domain-specific. See the No Free Lunch theorem.

Perhaps in some cases the fascination results from the idea that something so _simple_ could produce universal computation. Yet again, why should this be impressive? The fact that it is universal does not mean that we can actually make it do anything in practice. And in fact we cannot. There may be a simple CA that mimics the linux operating system, but good luck finding it. I'd rather just program it myself than use such a clunky pointless representation as a CA to try to cludge it together. So what does it matter that something simple produces opaque unmanageable complexity?

The overall question is, why is it at all compelling or motivating to point out that some CAs are universal? Isn't that just a distraction from the real issues?

ap

Report this post to a moderator | IP: Logged

03-06-2008 12:08 AM

Click here to Send aiprof01 a Private Message

Philip Ronald Dutton
independent
Columbia, SC

Registered: Feb 2004
Posts: 172

Re: Why Does Universality Matter?

Originally posted by aiprof01
In practice, what really matters in computation is getting the system to perform the computation that you actually want.

I think you are saying that the hard part is programming the system.

__________________
P h i l i p . R . D u t t o n

Report this post to a moderator | IP: Logged

03-06-2008 03:01 AM

Click here to Send Philip Ronald Dutton a Private Message

aiprof01

Registered: May 2006
Posts: 12

Re: Re: Why Does Universality Matter?

Originally posted by Philip Ronald Dutton
I think you are saying that the hard part is programming the system.

That's doesn't really capture my full intent but it's part of it.

The broader picture is that "programming" is only one way to create a system that does something desirable. A more general way is _search_, which means looking through different variations for one that does what you want. The important concept is the idea of a "search space," which is the space of all possible instances of the type of system you are dealing with.

Examples of spaces are the space of all DNA strings and the space of all C++ programs. Depending how you define such spaces, they may be infinite or finite, but they have very different structures, so you would approach finding an artifact in either space in quite different ways.

For the DNA strings, you would not really "program" them directly because they are not a language that was constructed with human intent. So DNA is better searched. C++ programs, on the other hand, are designed to be consturcted by hand, so they are meant to be programmed. Still, what DNA can do often programs never have been able, and vice versa. Both encodings have very different _search biases_. Even if both are perhaps "universal" in some sense, the kinds of things you do with either and the way you do them is quite different.

Of course programming really is a kind of search. Search just means creating a new instance of some type of system. But I am alluding to the intuitive process of the search: programming is a type of search that is very narrow. Many other search processes follow very different procedures, like hill-climbing search.

So again, look at this situation: it's the biases of the encoding that matter. What does it really matter in the end if C++ is "universal" or not? Or if DNA is? Would it detract from the phenomenal space of DNA, which includes human beings, if someone were to show there are many things it simply cannot represent? Of course it would not matter- the power of the encoding is not in its universality but in its bias (i.e. all of natural biology). The universality would just be a theoretical curiosity.

ap

Report this post to a moderator | IP: Logged

03-06-2008 03:21 AM

Philip Ronald Dutton
independent
Columbia, SC

Registered: Feb 2004
Posts: 172

searching

I believe you have to program the search. What I mean is that you still have to express, somehow, exactly what it is that you are searching for.

Translating your search parameters into a form that the system understands is a complicated programming exercise.

__________________
P h i l i p . R . D u t t o n

Report this post to a moderator | IP: Logged

03-06-2008 04:42 AM

aiprof01

Registered: May 2006
Posts: 12

Re: searching

Originally posted by Philip Ronald Dutton
I believe you have to program the search. What I mean is that you still have to express, somehow, exactly what it is that you are searching for.

Translating your search parameters into a form that the system understands is a complicated programming exercise.

Sure, sometimes you have to program your search, and sometimes you do not because you simply perform the search in your own head. Or, the search may be a product of nature that was not programmed either.

But I'm not sure in what sense we are addressing the question of why universality matters? Where are you trying to go with this line of reasoning?

ap

Report this post to a moderator | IP: Logged

03-06-2008 04:47 AM

Tony Smith
Meme Media
Melbourne, Australia

Registered: Oct 2003
Posts: 167

Universal as a minimum not as a universal

Almost six years after the NKS book came out, I still haven't written more than occasional notes about my problems with the idea that universality might allow us to ignore the impossible complexity of the data needed to do anything useful. But I also have not seen anything in those years to suggest that my objections are ill founded.

I can certainly see how Wolfram's twin expectations that (i) his Principle of Computational Equivalence is important and (ii) the next state of the universe is fully determined by the current state (via some universal rule) fit together well. I'm just everyday more convinced that he is ultimately wrong on both fronts, while remaining very appreciative that NKS has reenergised interest in emergent dynamics.

History is as overcrowded with theoreticians insisting on answers that are just too simple to work as it is with those trying vainly to return humanity to the centre of affairs. Real history is overflowing with unanticipatable synergies.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

03-06-2008 09:10 AM

Click here to Send Tony Smith a Private Message

Abby Nussey
Wolfram Research
Cambridge

Registered: Sep 2007
Posts: 20

Re: Universal as a minimum not as a universal

Originally posted by Tony Smith
History is as overcrowded with theoreticians insisting on answers that are just too simple to work as it is with those trying vainly to return humanity to the centre of affairs. Real history is overflowing with unanticipatable synergies. [/B]

Great point, Tony. Stephen Wolfram gave a talk at MIT last evening, and one of the things he said was, "If the Universe is reducible to a simple rule, like one which would generate a cellular automata, it would be ridiculous not to *try* to search for it."

Science is currently saturated with the idea that the FT is *so* complex in form we've got to use complex structures in mathematics, understood well by perhaps a couple handfuls of people in the world, to deal with it (see current trends in Algebraic Geometry and Quantum Mechanics; also String Theory, though I personally know less on that front). And perhaps the computation for something as complex as the universe is itself, complex. But perhaps it isn't.

At bottom, it would be silly not to exhaust all simple searches before embarking upon complex searches, especially since complex searching involve tools in mathematics that can take a significant portion of one's life to conquer.

With respect to "Why does universality matter.." again, forgive my naivete, but I think universality simply implies one *can* search. Searching for a program to do what you want it to do is certainly less efficient, when you want to do something comparatively simple, than building the program. However, when you have something reasonably complex, traditional methods (building complexity from simple, atomic expressions) can become as complex as the model itself. Therefore, it might make more sense to search through the space of possible computations (as long as you know what you're looking for, of course).

I'm new to NKS, so if someone can explain it better than I can (or correct me, if I'm wrong), please do.

Report this post to a moderator | IP: Logged

05-09-2008 12:02 PM

Click here to Send Abby Nussey a Private Message

Philip Ronald Dutton
independent
Columbia, SC

Registered: Feb 2004
Posts: 172

how to know it?

I keep wondering how you would know the "one simple" rule if you were searching for it. It has been a few years since I read the NKS book. Does anyone recall if Wolfram specifically mentions the problem of identifying the rule? You can't just simply "run" this rule on a computer because that computer is too restrictive of an environment (it doesn't "interface" to the whole universe). And if you did have Hardware that could "run" this rule to reproduce, then how would you distinguish it's output from the reality of your current universe?? I feel you are limited to the hardware that will run the rule. Therefore you can not be sure that you have the correct rule. I do believe it is worth considering the idea but the practical aspects of proving that such a simple rule is "THE rule" will be perhaps the most challenging task or perhaps impossible.

__________________
P h i l i p . R . D u t t o n

Report this post to a moderator | IP: Logged

05-10-2008 03:46 AM

Last Thread Next Thread

Show Printable Version |

Email this Page |

Subscribe to this Thread

wolframscience.com | wolfram atlas | NKS online | web resources | contact us

Forum Sponsored by Wolfram Research