[Most successful application thus far?] - A New Kind of Science: The NKS ForumA New Kind of Science: The NKS Forum
Pages:1
Most successful application thus far?
(Click here to view the original thread with full colors/images)
Posted by: AdamL
Hi all,
I'm new at this and fairly "green" when it comes to mathematics in general, so please forgive me if this is a silly question :-)
I wondered if there was a particular problem or idea towards which NKS most perfectly applies. I think it would be useful to see where NKS fits in relative to other fields of knowledge. The book does a good job explaining how broadly it applies, certainly, thus far. Yet it is hard to say what this field of knowledge *is*. What is NKS the study "of"? If someone asked me if it was a physical science, I would have to say no, because it's not really a study of anything physical; It is closer to mathematics in this way. However, it isn't a sub category of mathematics - is it? What is NKS? The study of...? Where does NKS fit where no other branch of knowledge does not?
Posted by: Dan Ellwein
It's another way of describing the apple fall from the tree...
You can think of Stephen Wolfram as a new kind of Isaac Newton...
Instead of seeing science through the eyes of mathematics (equations),
Stephen Wolfram sees the world through the eyes of simple programs...
Stephen Wolfram has discovered that even with something as
simple and elementary as one dimensional cellular automata's,
unexpected complexity can be produced...
This complexity is so rich that the only way to capture it is by
letting the program run and see what happens...
No equation can capture this complexity...
There is no short cut to this complexity...
This complexity happens effortlessly, it has a very low threshold...
Biological evolution can not account for this complexity, but simple programs can...
Human thinking is no more complex than a one dimensional cellular automaton (Rule 110)...
The reason the 2nd law of thermodynamics holds true is that we are no more complex than the processes we are observing...
I hope this helps...
Posted by: AdamL
Thank you :)
Posted by: Jason Cawley
The single most successful use of NKS and specifically CA methods, I'd have to say, would be fluid mechanics simulations, especially using lattice Boltzmann methods (an extension or refinement of basic CAs, allowing real number values at each site location). Most of which predates publication of the book, of course. It was helped along considerably by Wolfram's earlier CA papers back in the 1980s, which e.g. proved that the limit of a fluid CA as the number of cells increases is the standard Navier Stokes equation. Since the continuous equations get hard to solve rapidly (in more complicated configurations of flow etc), lattice methods on modern computers dramatically extend the range of problems that can be solved in practice.
CA methods have also been extensively used in ecological modeling, geology, traffic simulation, biological modeling of e.g. pigmentation patterns or growth processes. There are patents from NKS algorithms for random number generators (including Wolfram's original one) and various other computer science uses (fast binary digit counters e.g.), some filed by Hewlett Packard scientists. In this broader sense, I'd say modeling and especially modeling complex spatial processes, is the leading area of application, with practical and theoretical computer science uses probably second. There has also been a fair amount of pure math coming out of NKS, including theorems about logic and others about recurrence equations.
Posted by: AdamL
So just to be clear, NKS is first the idea of systems with simple rules, and the applications are approximate? Or does it try to be a model of something first?
Posted by: Jason Cawley
NKS studies the behavior of simple programs. Pure NKS is interested in what various families of simple programs typically do. You can think of this as being a sort of pure mathematics of short programs. Applying NKS means looking for real systems that behave the same way, or in a similar way, to some family of simple programs previously investigated, or to specific modifications (or subsets) of them, "tweaked" to fit the applied domain.
Just as in mathematics we can ask about all the conic sections, the trig functions, the simplest differential equations, and can then scan natural or engineered systems looking for cases that follow this equation or that, in NKS we can ask about the typical behavior of cellular automata or sequential substitution systems, and notice the class of behaviors that typically result. We can then scan real systems for those behaviors.
Sometimes we deliberately set up a type of simple program so that it must have characteristics we have in mind for a system it is meant to model. For example, CA models of fluids use specific cellular automaton rules that preserve the number of particles and also conserve vector momentum. Which lets us prove things about the "limit" behavior of such a CA as the number of cells increases (Navier Stokes equations of fluid flow, in my example).
Whether any formal system is an approximate or an exact duplicate of a behavior seen, depends on what is really going on in that seen instance, obviously. Generally speaking all formal systems are cleaner than empirical ones. But for the specific process being modeled it can be effectively exact. (Think of exponentials and interest on the one hand, or radioactive decay on the other). In principle you can also go the other way, and e.g. ask questions about an equation using a pendulum or an electronic circuit, instead of the other way around.
This isn't specific to NKS. It is just the usual math to empirical relation. In NKS, the convention is to call the first "pure NKS" and the second "applied NKS", but that terminology is just a convention. When you ask specifically about application, I naturally think of applied NKS examples.
Posted by: Philip Ronald Dutton
Originally posted by Jason Cawley
..... in this broader sense, I'd say modeling and especially modeling complex spatial processes, is the leading area of application.....
By the way, how would one re-cast the NKS PCE (principle of computational equivalence) in terms of "patterns" or what might be said of such complex patterns? Perhaps one might say, "you can only recognize or discover patterns up to a certain complexity cut-off."
Any thoughts or links to such discussions?
Posted by: Jason Cawley
I'd say we can be pretty good at it, better at it than one might expect. It is an interesting question. The NKS book discusses it in the perception and analysis section, especially the issue of texture recognition. On page 578 Wolfram shows a variety of CA generated textures that all share the same overall density. We are readily able to distinguish them, and see clear "lines" where one patch ends and another begins. The interesting question is how we do this.
Wolfram gives one piece of an answer on page 581. He shows that the different textures have different block frequencies, if one counts all possible 2x2 patterns. One can think of that as one dimension of classification, and then add another for larger blocks, and so on. Eventually one might have enough cross-cutting distinctions to fully classify and therefore distinguish each pattern.
But I suspect we use other tricks simpler than block frequencies, beyond a certain size. CA pattern recognizers can be written that readily detect certain sorts of features (straight edges e.g.) by just taking one CA rule and running it for a few steps on the data. Some rules will have the property that only certain structures in the original will "survive" a few steps in the "CA processing" of the original. We had a summer program student one year who worked on this, and adding cluster analysis to this idea, was able to write a decent CA based texture discriminator. His name was Zhe Hu, and his bio can be seen here -
http://www.wolframscience.com/summe...cipants/hu.html
Now, you might still fairly ask, isn't this approach going to fail eventually at some point? Probably, though right now we can't quite get computer classifiers (including other methods like neural nets e.g.) to match what our eyes can do, so presumably it can be pushed farther, profitably. At some point though, PCE suggests we will arrive at patterns that are effectively indistinguishable by our available methods of analysis, but nevertheless differ in small details. If the process that laid down the pattern is at least as complicated in information processing terms, as our reductions afterward to compress or classify that pattern, then eventually we hit diminished returns, and we'd have to go through as much computational work as the system itself, to "see" any originating order in it.
One clue we are fairly close to this in pattern or texture discrimination is order illusions. By which I mean, we tend to see some forms of order even in patterns we have deliberately made by entirely random processes. Our subjective-perceptual methods of classification will sort random noise by the small scale structures that arise within it by happenstance.
Obviously, since the number of possible patterns of a given size is exponential in the size (square of the range for 2D cases), when we classify we are lumping huge classes of possible patterns together - because there is no way we could possible distinguish the full number, each from each other. In that sense our pattern classifications are always "lossy" or contractive maps. This works better than we might expect because processes making patterns are usually less than perfectly random, and can't really reach that whole space.
Anyway, as I said it is a good topic. The obvious technical thing to do within it is to try to write really good texture discriminator programs. Where they can't be pushed any further, you should be bumping up against PCE. But you won't know how far that is until you try, and see how far you can get.
I hope this is interesting.
Posted by: Philip Ronald Dutton
It is interesting when thinking about Patterns in terms of NKS. Specifically, when thinking about financial patterns of some organization, there will be specific patterns that persist over time (and even spatial patterns- not just in terms of "3d"). Even economic patterns are also the topic of "data mining."
Interestingly, companies that employ "data mining" techniques often think that they should just get more data to improve the analysis. Then, they reach a threshold and are not totally satisfied because they want even more power in their analytics. So they employ advanced techniques beyond the standard generalized linear model. However, PCE implies that ultimately, you will not be able to data mine past a certain point.
This is quite interesting to me now that I think about it. Obviously the NKS literature already suggest this but it took me a while to see the data mining and pattern recognition angle of NKS PCE.
I think some industries have done well to map their "perpective" into something like a generalized linear model but they don't really consider PCE. Not considering the implications could mean lots of wasted money on the promise of data mining.
Assuming you could data mine to the moon and back and have an analysis of your business' economics which is very good, it may not turn out to be useful for prediction. Certainly you can make the prediction but if you also ACT on the analysis then you might change the system such that it does not meet your predictions. This thought is kind of an initial thought experiment I had as I tried to synthesize NKS PCE with "Systems Thinking" (a systems analysis methodology introduced by Sanger).
It would be fun to start a thread where the synthesis of NKS PCE, Systems Thinking, and Data Mining/Analytics might take form. I like the triangle of these topics. Any thoughts?
Posted by: AdamL
I used to do a fair bit of data mining but never encountered anything like a pattern in terms of rule systems producing complexity. The closest I got to anything like science was more a statistical accounting. I'm curious how NKS would be applicable to a database, say around 35,000 records for sample size, each record having 20-30 common fields.
I don't think I am understanding the relationship between NKS and the universe yet. I can see that the model exists purely in theoretical terms with no dependancy on empiricism outside the theory. (ie., empirical observation is useful but mostly within the framework of NKS) I have no problem with that, philosophically. I notice though that nothing like the precision of mathematics in physics exists for NKS. I think Jason will diagnose where I'm at, but here is an example: when the earth orbits the sun, the physical explanations involved are not purely theoretical, they could be derived empirically. There is no primacy of a model before the system itself. For the same reason "we" get an uncanny precision in physics that confirms what we do in the theoretical beyond a doubt. There aren't approximate correspondences to physical science in orbital mechanics; The correspondence is exact and it doesn't settle for roughly predicting this or that orbit.
NKS on the other hand seems to have a different relationship to reality than physical science. For NKS, the theory is the primary thing (it seems to me) and the applications in the world are approximate, if not coincidental. The "NKS Kind of Thinking" means something, but not the way physical science does. There is a thread in that forum that talks about the Mozart problem and the limitations of models. Is a model dependant on empirical evaluation to be valid? Physical science tends to think so, NKS seems to break from that tradition. For NKS, it seems that the theoretical possibilities do not get to the level of modeling actual systems. The idea maybe could be described as a "demo" science - NKS alludes to a reality through a general model, it does not reproduce that reality with the model. It doesn't have to reproduce anything to be "real" knowledge.
I'm an imaginative person and I like analogies. To me, NKS is a glimpse through a peephole. i.e, the CA or the systems themselves are abstractions.
Posted by: AdamL
bump - Dan? Anyone? Is this even accurate?
Posted by: Dan Ellwein
Adam
Here is an excerpt from Stephen Wolfram's opening keynote speech - NKS 2007.
This might help with understanding models in the context of NKS:
"When I started working on NKS, I really started from a traditional scientific paradigm. Of trying to find formal models for the natural world.
And what I realized was that there was a vast expansion of those models that could be made. Going beyond three centuries of traditional mathematics. And looking instead at the more general kinds of models that can be represented by programs.
But increasingly I've realized that it's that computational universe of possible programs that's ultimately the most important thing.
Yes, the programs can be used as models, and that's an important application.
But ultimately the most important intellectual contribution of NKS is simply to recognize the importance of exploring the abstract computational universe of possible programs.
It's what I call "pure NKS". The basic science of the computational universe."
The full speech can be found at:
http://www.stephenwolfram.com/publi.../talks/nks2007/
- Dan
Posted by: AdamL
Why is it more important to study what computer programs can do than try to model things which exist outside computer programs?
To put it another way, if I was primarily interested in the whole of reality and not just the particulars of CA, what appeal would this have for me, if any?
My hypothesis was that, at least if there was some intersection between the world of computational programs (i.e., CA?), then Wolfram's science would be appealing for what it revealed about the universe.
If it doesn't go farther in it's intersection with reality than the programs themselves, I'm not sure what the appeal is, other than the beauty of it. That would make it less relevant for it's applications than it's beauty.
I guess I am still not clear exactly what he thinks the relationship is between computational programs and our universe. I know for some scientists the two are virtually unitary, but I have not seen a statement to that effect by Wolfram.
So I remain a little stumped as to where he wants all this to fit in, if at all, with the rest of the universe.
Posted by: Jason Cawley
The universe computes. Humans figured out what computation is as a formal artifice, originally, but that isn't essential to computation. In fact, all the computations we manage to carry out in the real world, we do by piggybacking on the ability of nature itself to compute, arranging bits of that ability to our purposes. Otherwise put, we live in a programmable universe, or we would not be able to get to square one with practical computers. But even without any such arranging, nature has been computing all along - we just didn't know enough about what computation was, to notice it, or to think of it in those terms.
Now we do. And computation can thus be seen as what it is - no longer as an artificial thing separate from the natural world, or limited to systems specifically engineered to have computational flexibility as a property. It is a formal phenomenon, which occurs in nature as well as in engineered systems. It doesn't need any intention to arise as a phenomenon - it is simply a formal property of all sorts of systems, including natural ones. In other words, shattering the natural-computational dictotomy implicit in your question, is exactly the point.
How do we arrive at this? From both ends - studying computation formally to see how little it requires, we notice that the threshold of computational sophistication is so low, that plenty of systems nobody suspected or meant to have it, do have it. And empirically, we see all sorts of patterns in every field that we can see arise by essentially computational processes - simple ones, that don't need much in the way of components or element-by-element sophistication, but that can nevertheless produce behaviors as complicated as one likes.
We knew already that nature "does math", in the sense of behaving according to mathematical relations - and now we also know that nature computes, in the sense of behaving in ways that depend with arbitrary flexibility on exact details of environment or initial conditions, in the same way the behavior of a modern digital computer depends on the exact details of the specific program fed into it.
Posted by: tomjones
That argument to me sounds like a repeat of a similar argument that has been made over the centuries where it always seems to be that people like to think the world works how the most complex technology of the time does. For example many years back people thought the world was a giant clock now people think its a computer, and I am quite sure as soon as something better comes along NKS will in a sense be reborn with that new technology as its base.
Also your point on how little is required for computation is actually incorrect, NKS is only possible because of the carefully designed digital computers, the computation could not happen purely by chance nor did they. What goes on around us in the world you can choose to think of as computation if you wish, but ultimately it is not a particularly important point. For NKS its importance is derived from the claim that studying abstract computational systems is a valuable enterprise.
Computation the idea of it is a human conception and has nothing to do with nature, the reason we can do computations in the world is because the world is orderly and behaves by defined rules. That is the key to making computation possible, whether computation has anything to do with nature is only meaningful insofar as it applies to better understanding the world around us.
The concept of computation can be thought of as a temporary bucket we use to develop ideas and theories about the world but thats it.
In fact the best theory that one is going to come up with for how nature works is going to be the one that most closely duplicates the way nature does things. Theories with all manner of levels of abstraction muddle the issue due to the fact that there is a significant amount of work required to get back to the system you are trying to model.
Thanks
Posted by: Jason Cawley
It is fair to note the historical tendency to think of nature in terms of man's latest tech, and specifically to compare present focus on the computational aspects of nature to prior focus on the mechanical aspects. But of course, mechanics are much more than a metaphor - they remain the core of physics. It is not a mere analogy that physical systems are mechanical systems - whatever else they are.
Similarly with computation, it is not a matter of chosing an analogy. There is a specific formal fact that makes general computation possible, and it is what I am referring to when I say it goes on in natural systems. That fact is the independence of specific computations from the detailed underlying operations used to carry them out; otherwise put, the instruction set does not have to change for the computation to change.
The reason we can make general purpose computers is not simply that nature is orderly and follows rules. It is, instead, that there are small sets of underlying operations available, which can perform any feasible computation by just being interleaved in different ways. You don't need to add a new instruction to the set to reach a new space of desired behaviors. You can instead just interleave the elements of the instruction set differently.
Not every set of possible instructions or underlying primitive operations have this characteristic. Early on in the history of computing, it was thought almost obvious that only sets of instructions specifically designed to have this property, would have it. But that intuition was incorrect. Instead, once we fully understood the phenomenon (called it "programmable flexibility"), we found more and more formal systems that exhibit it, including much simpler ones that expected. And we started seeing instances of systems in nature that easily get to the threshold of internal complexity required, and show a similar range of resulting possible behaviors.
Looking at complex behavior in nature, one might think in each specific case that there has to be something special going on in the particular components that make up that instance of complexity - say in fracture, or dendritic patterns, or turbulence - but this is almost certainly incorrect. Instead the same formal fact probably underlies them all, that these are systems internally complex enough to support programmable flexibility, and they therefore naturally show the same range of behaviors (or behaviorial classes, if one prefers) as general computation.
Just as systems with widely different underlying components can all behave as fluids because they follow the same conservation laws in their mechanical motions, or be described thermodynamically becuase the same statistical laws apply regardless of components, systems over the threshold of computational sophistication will show the characteristic range of behaviors seen from computationally sophistication (aka "universality", up to some limit idealizations).
This tends not to be appreciated by researchers with little internal knowledge of how practical computers actually work, or the principles that allow general purposes computers with unchanged and simple underlying instruction sets. If one thinks of artificial computation as a "black box", with human ingenuity inputs and outputs meant to be significant to human thought "post processing" only, one can miss the underlying formal point.
Find the underlying instruction set used in the natural instance under examination, and then formally test the limits of what different interleavings of those instructions can do. If you find they can do anything - any feasible computation - then you know that the possible complexity of that natural system is "unbounded above". You might still constrain the input space, or find all sorts of regularities in the outputs, at a suitably coarse grained or ensemble level. But the detailed output behavior may depend on the detailed initial conditions, according to an involved ongoing computation as complicated as anything possible in our universe. When that is the case, it is not a metaphor to say that the natural system in question is computing. It is just a more exact understanding of what it means to say of anything that it "computes".
Posted by: tomjones
You are correct to a point, but it is also the case that the more one abstracts a system the more complex the model becomes, since the distance between the way the model works and the way the actual system works is so large.
When it comes to current computers, or as you put it artificial computers there is nothing simple about the instruction sets. I am not sure if you have ever written a computer instruction set or read one for the intel processor that your computer probably uses, they are extremely complex. They are constantly changing instruction sets and adding more instructions to them, for example the current intel instruction set is something like 2000 pages long when written out. In fact there is nothing simple in current computer design and this is one of the problems just how inefficient current computer design is becoming.
As to the question does computing gets us closer? It is I would say up for debate, since computation no matter how general your notion, if it is the formal one that has developed, I would argue the abstraction is still to far away from the way actual systems in nature work. Now I am quite aware that this is always the case and one is always mapping one system onto the other but one it would seem could get closer to the way things work. Ultimately as soon as some new technology whatever replaces computers comes out NKS will be re devised with that new technology at its base, if history is a guide.
"It is a formal phenomenon, which occurs in nature as well as in engineered systems. It doesn't need any intention to arise as a phenomenon - it is simply a formal property of all sorts of systems, including natural ones."
This statement is partially false of course, computation needs intention or purpose to arise, if you don't believe that try taking apart a computer putting the pieces in a bag and then shake them up and see how long it takes for a computer to pop out. This is of course ridiculous and it is ridiculous even in simple cases. I find it amusing since none of what NKS has "discovered" could be done without computers which are carefully engineered or without carefully organized searches, there is nothing unintentional about NKS methods. Whether computation is at the core of things or not it will never be a purposeless phenomena or one that just happened to come about.
"But even without any such arranging, nature has been computing all along - we just didn't know enough about what computation was, to notice it, or to think of it in those terms. "
False, this is not the case nature was arranged to compute if you want to use that term, computation is an arranged phenomena. Noise times noise always equals noise if you start with nature as random or unintentional you will never get computation out of it. This is a formal fact of computation and the necessity for certain properties to be there for computation to take place. For example even simple systems like CA cannot happen by accident or without design there is a formal way they work and a formal design that they follow.
Thanks for the reply
Posted by: Paul B. White
Jason,
I'm getting the impression that NKS people assume that the computer which generates the universe (call it the "fundamental computer") must be of the general purpose type; i.e. capable of doing all kinds of various and sundry computations. Is that a fair assessment? If so, I would like to point out a few problems with that.
At the fundamental level, I would argue that the universe is not so complex that it needs such a flexible computer to generate it. In fact, the basic output of the fundamental computer may only need to be a few symmetries and couplings, plus the action quantum. The rest of what we experience (e.g. space, time, particles, daffodils, etc.) could simply be fields that emerge from those things. So, if the stuff of the universe is fundamentally simple, why would nature choose to use a general purpose computer to produce it, when it could use a simpler, less “expensive”, special purpose computer for the task?
I mean, it would be shocking if Hewlett-Packard specified a Pentium to do the computations for a simple adding machine. Likewise, I think it would be shocking to learn that nature uses a general purpose computer to generate the fundamental stuff of the universe. IMHO, it would be an example of profligate waste and inefficiency at the heart of the universe.
I think a lot of NKSers are too enamored with the notions of general purpose computers and universal computation -- and this could be a stumbling block to seeing how things work at the fundamental level, since nature doesn't care about the aesthetic appeal of those things to humans. Rather, it is a good bet that nature cares only about doing stuff in the simplest possible way, whether it fits our aesthetic expectations or not.
Posted by: tomjones
Paul, you are missing one key point no matter how you think about things, particles will come about early on and if you look at particle physics things get quite complex quite quickly. Further if there is a computer of some sort at the center of the universe, which I doubt, it is unlikely to look like any computer we would recognize, but that system no matter what it is, will have to generate an enormous amount of complexity, very early on.
The other thing to take note of is that Wolfram seems to believe that the fundamental stuff of the universe may well be a network of connections that change based on patterns of connections.
I think the point of NKS making to much of computation is a valid one but it plays into a point I already made of NKS fitting the classical historical role of the most complex technology being like nature, just like people used to think the world was a giant clock.
Thanks
Posted by: Jason Cawley
Paul - yes simplicity is likely to be a good guide. Wolfram suspects that even the initials of a fundamental rule will be simple - or at least, that we won't find it unless the initial and rule are both simple, a significantly easier claim. But the underlying rule is likely to be universal.
Why? Well, if every phenomenon nature shows were simple, then I'd agree with your argument, that universality would be "formal overkill". But instead we see all classes of behavior. And we know which class of formal system exhibits all classes of behavior, and it is not the simplest class.
The math of traditional physics stresses all sorts of symmetries, in part because those make it much easier to solve things. But while we see gobs of symmetry at a fundamental rule level, the universe is not remotely simple, symmetry, periodic, fixed point-ee, or anything of the sort.
And we have formal precedent for systems evolving according to simple underlying rules, with plenty of low level structure and regularity caused by the form of the rule, that nevertheless generate elaborate complexity and variety, even from very simple initial conditions. They are computationally irreducible underlying rules.
That is enough to suspect that the underlying rules, whatever they are, will be at least that high in the computational behavior scale. Whether irreducible and universal usually coincide, is of course an open NKS question, and Wolfram's PCE amounts to the conjecture that they will. If that is true, then the previous will extend to "the underlying rule is probably universal".
Which doesn't mean that it will have some incredibly elaborate initial, exploiting that inherent flexibility. You can start a universal rule off simply. When you do, you still get lots of its inherent potential variety, since subpieces of the evolution pop up here or there in the pattern, that mimic different initials (or more strictly, pieces thereof). That's the idea. It is a possible explanation for the mix of variety and simplicity we see in nature.
It could be wrong, of course. It is a conjecture, and a fairly heroic one, as extrapolations go. But we have evidence against overly symmetric and simple alternatives, from the lack of perfect simplicity or regularity seen in the history of the universe.
Now, sure, some alternate explanations have other ways of generating that from relatively simple formalisms. But if they invoke objective chance to get there, they haven't really explained it. Instead they underspecify a universe. You can get a nice symmetric ensemble of possibles and just let objective chance pick one, but then the symmetry is entirely imposed, really.
I suppose I should add that you are right that too much should not be hung on universality alone. If someone seeking fundamental computational rules for physics just relies on an argument of the form, "rule X is universal, so it has some possible initial condition in which a computation parallel to the universe can in principle be found", that is a weak argument.
The NKS book does not do this. Instead, Wolfram considers and rejects numerous possible computational schemes as unpromising, when known physical relations or symmetries would be too artificial in that set up. E.g. straight CA models do not naturally produce spatial isometry (they tend to have preferred directions along lattice "grains"), so they are out. He wants a set up in which curved space is natural, relativity works, etc. In that sense, you are right that a focus on known simplicities has to guide any search for a computational model for physics.
FWIW...
Posted by: Jason Cawley
tom - Well, your conventional view on the subject has the merit of showing by contrast that the NKS book has a definite result, and not one that was (or is) intuitively obvious to most people. And it is understandable - the intuition we get from engineering is that one only gets a lot out of a system if one put a lot into it. What cures this intuitive mistake, though - and it is a mistake - is the practical question that Wolfram started from: what do entirely random examples of simple computer programs actually do?
Not programs designed to do something or other. Just simple ones. Not carefully engineered searches designed to find something that will satisfy condition X - just exhaustive search, aka looking at every single one of a small enough class. And no, one does not have to shake the things forever to find anything non-trivial. On the contrary, the simplest rule sets ever looked at already contain instances of arbitrary complexity, and even of proven universality.
Modern instruction sets get somewhat involved to meet various engineering desires, especially to make it obvious to human programmers what is going on. Also to make certain common computations the simple ones in the instruction set used, instead of requiring moderately elaborate sequences of more primitive operations. But no new possible computations are reached thereby. All that happens is that a permutation is done on the same set of computables, and the number of steps needed for some goes down (while that for others goes up).
That general computation is possible at all, that the idea of a fixed instruction set works, is not dependent on anything running thousands of pages. On the contrary, it was noticed that the limited idealized instructions of lambda calculus, Turing machines, and arithmetic, all reach the same space of possible computations.
One might have still thought at that point, and most did, that only systems designed to mimic processes of human reasoning, could have the property of universality. But today we know better - there are just far too many very simple systems proven universal by now, which no one "meant" to have that property. It didn't take a billion monkeys a billion years to find them either. All that was necessary was for someone to ask the question: what do typical simple computer programs, that haven't been picked for any specific reason or designed to meet any desired objective, actually do?
That is the issue standing on the doorstep of NKS. Whether you are interested enough in the answer to step inside, well, that is entirely up to you.
Posted by: tomjones
Thanks for the reply...
I would agree that whatever the fundamental model of nature is, it is most likely simple, for the reason that any system that achieves the complexity of nature would necessarily need to have an efficient way of getting to that complexity which means not using excessive numbers of steps to get anyone place.
So the issue to my mind is not computational space reached but rather the efficiency of the computation. By this I mean for example if we take a classical Turing machine we could in theory encode all the operations that a current computer does, but computing a floating point operation on a Turing machine is wildly inefficient, thats why one uses specialized instruction sets.
The argument about universality and simple programs sounds to me a bit like saying why get a hammer to pound in a nail when I can use my shoe. But maybe this is because I am not quite getting the NKS view.
Further it seems to me that it is also an issue of is the complexity generated equivalent? Is the complexity generated by a simple program the same as the complexity we see in nature?
It seems to me that complexity generated by a simple program while it may be universal would have difficulty in dealing with a system where the output of the system has little to no resemblance to the underlying components?
For example we know that we are made up of atoms but those fundamental components and their behavior has really nothing in common with the final behavior of a human. So to take this back to NKS how would NKS deal with this can it deal with a system where the output of the system shares no obvious relation to the starting primitives, unlike CA where there is an obvious relation between the cells and the output behavior.
I hope this makes sense...
Thanks
Posted by: Jason Cawley
OK then, I'll bite - what is the obvious relation between the behavior of the emergent particle patterns in say rule 110 - which occur as the "joins" between two regions each "tiled" by periodic backgrounds, of the same or of different types on either side of the "join" - and the behavior of the cells? Can you deduce the behavior of every particle-pair "collision" in a rule 110 evolution from the form of the rule itself, without carrying out the computer experiment of evolving an instance of that collision and seeing what happens? (See the example at the end of chapter 2, starting on page 31, if you don't know what I mean by interacting rule 110 "particles").
No, see, you can't. The behavior up at the combined-cell particle level has no obvious, intuitive relation to the form of the underlying rule. Even though it is a strictly logical consequence of that rule. The reason for the apparent difference in the two statements is that sometimes strictly logical consequences are involved enough that they are not at all obvious, and there is no faster way to figure them out than to carry out the evolution in question. Aka to do the same computational work the system does as it evolves.
In practice, just to enumerate the possible particles on a say 20 by 20 region of a rule 110 pattern, involves a large exhaustive search - and once each is found, another exhaustive computation to see how each interacts with each of the others, when it is just one of each - at each of a range of offsets or "phases" to each other. You are rapidly up to the scale of millions of interactions. Extend the pattern width considered to 100 wide, and the number of possible interactions rises exponentially. Wide enough (still perfectly finite), as it is more than the number of actual particles in the universe.
And that is just one instance. So we are never going to know them all by a priori reasoning. In practice, the status of how one class 4 particle interacts with another is an empirical issue to be determined by formal experiment, with basically the epistemological status of any other brute fact of "nature". We say, the emergent level follows its own logic. Not because it can't be determined from the bottom up in this or that specific case, but because doing so is so hard and inexhaustible, they are effectively independent subjects of knowledge. Just like chemistry and atomic physics...
Posted by: tomjones
In a CA if you look at enough output you can deduce the rules that generated it. In nature, there are many systems that looking at the output you can't deduce the starting rule no matter how much output one has. I was speaking from the top down not from the bottom up. It is these type of systems I am speaking of, these don't seem to be classifiable in NKS, where one would need one set of rules and primitives that evolve to a point where they generate a new set of rules and primitives and so on.
I realize there is no way to know before hand what the result will be...
A bit of an aside, I just picked up Mathematica 6 and I must say I like it so much more then MATLAB which I have been using for years, and I have been playing with some NKS experiments...
Thanks
Posted by: Paul B. White
Jason, I agree that the generation of our universe involves simple computations of some sort going on at a fundamental level (see my paper, "Particle Genetics and Expression" posted in another thread).
But I am confident that nature, like an engineer, is going to use the simplest system and components that will get the job done. General purpose computers are nice for running Linux, word processors, web browsers and spreadsheets, but the basic stuff of the universe is much simpler than that. Nature is not profligate, and so it will use just what it needs.
Take biological genetics as an example. Nature uses a sequence of exactly three nucleotides to specify an amino acid. A sequence of two would not be enough to specify 20 amino acids; and four would be a profligate waste. The minimum that is necessary to do the job is a sequence of three, and that is what nature uses.
Another important thing I think everyone is missing is that the system which generates the stuff of the universe is not going to be logically flat. That is, the components of the system are not all in the same logical plane. There is a kind of “z axis” in the universe's logical space, which produces a hierarchy of levels with concomitant dependence and independence relations among those levels. These built-in logical relations are the “rules” that do the computational work. They don't generate colored cells like a CA; rather, they generate fundamental couplings and symmetries. We don't need to specify these rules via software or initial conditions -- they are built in from the get go. So you don't need to feed in software from the outside and you don't need a “programmer” to write the code. This, I believe, is the apex of simplicity -- Occam's razor in its finest form, reducing everything to the bare minimum that you need to get the job done.
For evidence in physics of this underlying logical hierarchy, look at the different scopes of the fundamental interactions. As you go from gravitation to EM to the strong interaction, the scope gets progressively smaller. Gravitation has universal scope (i.e. it affects everything); EM has intermediate scope (affects a lot of things, but not everything); and the strong interaction has a very narrow scope (affects only a small band of things).
What does this scope pattern remind you of? It reminds me of the nesting of logical blocks within a proof (or, similarly, the nesting of statement blocks in a computer program). The initial premises in a proof have universal scope (i.e. logical priority to every other part of the proof), and can be asserted anywhere in the proof. But a nested assertion such as "Now suppose that blah blah...", forms a logical block that has limited scope within the proof; and another such assertion within that block forms another nested logical block with an even smaller scope; and so on.
The fundamental interactions exhibit this same type of scope pattern, and so it is reasonable to suspect that there is logical nesting going on, and thus a fundamental hierarchy of levels. These levels aren't separated in physical space and time, they are separated in a logical space, and, together with their concomitant dependence and independence relations, are available everywhere to do the computational work of generating couplings and symmetries directly, and (via emergence) fields such as space, time, and particles.
If you are interested in learning more about my system, read the paper “Particle Genetics and Expression”, which is attached at the beginning of the thread A candidate simple program for generating fundamental physics.
Posted by: RLamy
The meaning of the output is purely in the mind of the observer. In principle, you can use Rule 110 to render a photorealistic image of the Eiffel Tower starting from a 3D-model. The complicated, and at first sight random, pattern of gliders you will obtain as output will have exactly the same relation to the Eiffel Tower as the complicated pattern of bits (conventionally called a JPEG file) you would have obtained if you had chosen to use your computer with suitable software.
By definition, starting from any computationally universal system, you can build a tower of emulation of universal systems. At each level, you can completely forget about how the previous one works, remembering only the translation table between lower-level patterns and higher-level primitives. In that case, it is perfectly natural to ascribe to the lower-level patterns the meaning of the higher-level primitives.
The translation table can only be obtained through brute force computation. This means that going down a level is a hard problem even if you know what the lower system is. And remember that any universal system can emulate anything, so you can choose whatever universal system you want as the lower system. You can stare at the Eiffel Tower for as long as you want, you will never be able to discover rule 110, and looking at the Statue of Liberty or the Taj Mahal won't help either.
Posted by: tomjones
Of course you still have the problem that you universal system still can't model many phenomena, so they obviously are not as powerful as you make them sound. They are even further hampered by that fact that just because it can emulate something does not mean that its a good model. For example I could make Rule 110 emulate a current computer, and it could, it just be fantastically slow and inefficient.
As to the meaning of the output being merely in the mind of the observer, that doesn't fly, for example I can say x + a / b^2 = 3.196828 is the size of a proton. So in my mind the output of this system is the size of a proton.. this means nothing and is utterly ridiculous. I think what you meant to say was that one can map one system to another and assuming a proper mapping the output of the system that emulating will represent the system being emulated.
Thanks
Forum Sponsored by Wolfram Research
© 2004-2008 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