A New Kind of Science

A New Kind of Science is a controversial book by Stephen Wolfram, published in 2002. The book is available online (ed. see links below).
Contents 
Purposes
A New Kind of Science (NKS) aims to realign the way science is done with computational realities of our Universe. The intellectual structure it builds takes three forms:
 Pure NKS: The empirical, systematic exploration of simple computational systems for their own sake.
 Applied NKS: The use of simple computational systems, and the NKS methodology, to model systems in nature and for technological purposes.
 NKS way of thinking: How the computational realities of our universe impact general thought.
Relationship to existing fields
A New Kind of Science has its origins in the field of Complex systems research, which Wolfram helped ignite with his initial discoveries about Cellular automata in the 1980's.
However, by the 1990's Wolfram's thought had diverged significantly from the standard practice of the field, and focused not on understanding complexity as we observe in nature, but instead on more abstract computational systems.
Whereas Complex systems research tends to focus on simulating behaviors found in nature, Wolfram's "Pure NKS" has to do with exploring the behavior of very simple computational systems for their own sake.
Traditionally, mathematics has been the field concerned with the study of abstract systems for their own sake. In fact, almost every system considered in NKS  cellular automata, Turing machines, combinators, etc  was originally invented by a mathematician. Despite some theoretical work, however, these systems lie outside of the mainstream of mathematics, and there is no branch of mathematics whatsoever dedicated to their experimental study.
In comparing Pure NKS to both mathematics and Complex systems research, the greatest philosophical difference is the emphasis in Pure NKS on the discovery of completely novel behaviors and mechanisms using exhaustive experiments.
While Pure NKS can be thought of as trying to understand the natural programming languages of different kinds of abstract computational systems, Applied NKS can be thought of as trying to understand the programming languages of natural systems. While there are a great many fields involving computational applications, Applied NKS is not about taking otherwise available models and implementing them on a computer. It is about developing models that are true to the computational character of the system with no superfluous clutter, and then connecting the models to the more general body of knowledge that is Pure NKS.
Overview
The foundational observation of A New Kind of Science is that very simple systems are very frequently capable of great complexity. While isolated examples of this have been known for millenia, no fundamental significance was attached to them.
The surprising fact is that if one just starts enumerating simple computational systems, one very quickly encounters great complexity. This is robust fact that does not depend on the details of the system in question, but rather seems to be a generic law of our universe.
The fact that complexity is in fact rather easy to generate suggests an entirely new approach to science. The traditional path of science is to seek out examples of behavior in the natural world and try to break them down into understandable pieces. But an alternative path is to just systematically enumerate simple abstract computational systems, starting with the very simplest, and try to understand what they do.
The empirical fact is that they do a vast number of qualitatively different and unexpected things, and the goal of Pure NKS is to document what sorts of behaviors occur, and then try to understand them in as great detail as possible.
That Pure NKS should be relevant to the natural world is not immediately obvious, and a good portion of A New Kind of Science is dedicated towards erecting a paradigm to justify this venture.
Wolfram provides some examples of complexity in nature generated by simple rules in his book. Other scientists have found how, for example, varied patterns on the wings of fruit flies are caused not by complex genetic programming, but by the work of relatively simple molecular switches that use the genes essentially as a "seed" for a pseudorandom process [1] (http://www.primidi.com/2005/02/09.html).
The first argument that A New Kind of Science puts forward is that traditional mathematics is essentially a product of human history, and that there is no fundamental reason to think that the particular constructs of existing mathematics are in any way a complete, ideal or natural set of tools for describing the universe.
Wolfram makes this argument because he seeks to offer Pure NKS as a sort of generalization of traditional mathematics. Wolfram suggests that when making models of natural systems, scientists should think in computational terms and not be constrained by the traditional toolbox of mathematical primitives. His point is that natural systems follow their own set of abstract principles, and it is best to directly represent them as a process of evolution  that is to say, as a computational system.
The idea of Applied NKS is that scientists will see a behavior in nature and seek to explain it using a very simple computational system. If there is a body of Pure NKS research, they will be able to browse it for candidate models or other forms of inspiration about how their system might be achieving its behavior. Sometimes they will have to invent an entirely new kind of computational system to describe their concept of how things work  but when they do, they will keep it as simple as possible, and study it with Pure NKS methods.
Wolfram claims that his approach to science is essentially inevitable due to fundamental shortcomings in the current paradigm. Essentially Wolfram argues that existing science does not take computation seriously, and that NKS is the logical approach to science if one acknowledges the computational realities of our universe.
Principle of Computational Equivalence is the book's capstone, as it provides a single concept from which all the other theoretical concepts can be derived. It claims that all processes that are not obviously simple are of equivalent computational sophistication. From this single statement flows an immense number of implications, from the ultimate limits of science to the question of human uniqueness. These sorts of issues, when framed in the computational perspective of the Principle, constitute the body of the socalled NKS Way of Thinking.
Evidence
Wolfram makes many bold claims in A New Kind of Science. In the minds of many, the foremost claim is one of style rather than substance: that he is in fact establishing, as the title suggests, a new kind of science.
The empirical study of simple computational systems is the new branch of science in question. It cannot be readily fit into any existing field, as its subject matter and most especially its methodology simply do not belong.
That it is a kind of science is supported by the fact that its organizing principle is computation, rather than equations. Also, the fact that all of its knowledge flows from purely formal experiments rather than experiments on natural systems make it distinct from traditional science. Finally, the emphasis on simplicity as the first and foremost  rather than simply an aesthetic concern  gives pieces of work a unique character.
Beyond these issues of selfimportance, the book makes numerous specific scientific claims.
That very simple computational systems often achieve great complexity is well established.
To establish a connection between the abstract computational systems of Pure NKS and the natural world, Wolfram offers several forms of evidence.
The first is a general argument that the details of a system's components often do not matter. For instance air and water have different components, yet exhibit many of the same properties. Likewise, abstract computational systems might have completely different components from common natural systems, but still have common characteristics.
A more direct form of evidence is a series of models of natural systems. Wolfram presents models (some original, others recycled) for snowflake growth, fluid flow, leaf growth, phyllotaxis, shell growth, and biological pigmentation. In the abstract these models are no different from the computational systems described in the book; it so happens the same computations can be readily observed in nature.
The longterm success of these models is still unclear, but on a visual level they appear to capture the essential mechanisms at work.
On a metalevel, Wolfram demonstrates that general forms of behavior  such as fractals, sensitivity to initial conditions, formation of continuity from lowlevel randomness, diffusion and aggregation processes, thermodynamic behavior, conserved quantities  can easily occur in the world of simple computational systems.
Beyond applications to natural systems, Wolfram attempts to demonstrate the power of his method by looking at other kinds of traditional problems. For instance, a chapter is dedicated to proving a set of universal computational systems that are vastly simpler than any ever constructed before. Likewise, using Pure NKS techniques he discovers the shortest possible axiom for basic logic.
Wolfram's claims in the area of NKS Way of Thinking are more difficult to rigorously substantiate. There are essentially two claims of increasing scope and power.
The first is that computational irreducibility is commonplace. That computational irreducibility exists in our universe is a fact that follows directly from the existence of undecidable problems, such as the halting problem, which can be viewed as a special case.
If computational irreducibility only occurs in a small number of pathological systems  such as those considered by logicians  then we could expect to eventually describe the vast majority of the universe quite directly with mathematical equations. But if computational irreducibility is commonplace, we will have to turn to computational systems like those of pure NKS.
There is as of yet no known way to show a specific computation is irreducible. There are, however, many pieces of circumstantial evidence that computational irreducibility is commonplace. For instance, increasing numbers of simple systems have been proven universal, which implies that at least some of their computations are irreducible. Also, systems like Rule 30 have been investigated in great detail, yet little progress has been made in finding a closedform formula. Perhaps most importantly, simply the fact that complexity is so common in simple systems seems to imply that issues like undecidability should arise more frequently.
The Principle of Computational Equivalence makes the stronger claim that almost all computations that are not obviously simple are of equivalent sophistication. This goes against the commonplace notion that there is a hierarchy of progressively more complex systems.
There is currently no way to formalize this statement, and in fact the statement can be viewed in several different ways : a law of nature, as an abstract fact, and a definition of computation. Concerning the verification of the principle, Wolfram writes:
"But like any principle in science with real content it could in the future always be found that at least some aspect of the Principle of Computational Equivalence is not valid. For as a law of nature the principle could turn out to disagree with what is observed in our universe, while as an abstract fact it could simply represent an incorrect deduction, and even as a definition it could prove not useful or relevant.
But as more and more evidence is accumulated for phenomena that would follow from the principle, so it becomes more and more reasonable to expect that at least in some formulation or another the principle itself must be valid."
Criticism
The book has attracted several types of criticism.
Plagiarism
The first is plagiarism: it has been claimed that Wolfram did not really present any new ideas, but essentially just elaborated on Konrad Zuse's old book on computable universes and cellular automata (Calculating Space, 1969, translated by MIT in 1970), without giving proper credit to Zuse, and actually misrepresenting Zuse's contributions in a selfaggrandizing way. Wolfram also was accused of largely ignoring and improperly referencing the prior work of Edward Fredkin on reversible digital physics (Fredkin published several papers on this topic after Zuse visited his lab at MIT, and published a widely known and freely downloadable book draft in 2001). Similarly, Wolfram's statements on Turing machinecomputable physics were criticised as a rehash of a paper by Juergen Schmidhuber, published in 1997. Wolfram was also criticised for downplaying the role of Matthew Cook, who apparently proved what was called the book's most interesting though not earthshaking result (about a particular cellular automaton).
Basic premise
The second type of criticism comes from people who do not accept the book's basic premise, namely, that realworld patterns may be the result of the execution of very simple programs. These objectors argue — much like a majority of quantum physicists — that Wolfram's models belong to the class of theories with local hidden variables which have been ruled out experimentally using Bell's theorem. Many of them also worry that the continuous symmetries that apparently exist in Nature — such as rotational symmetry, translational symmetry, Lorentz symmetry, electroweak symmetry and others are difficult to reproduce in the framework of "digital physics". These critics implicitly also doubt the earlier work by Zuse, Fredkin, Schmidhuber, Petrov, and others.
Vagueness
The third type of criticism addresses the vagueness of some of the concepts in the book, such as Wolfram's allegedly fuzzy notion of randomness, which contrasts wellknown mathematical definitions of randomness such as Kolmogorov complexity. Similarly, Wolfram's principle of computational equivalence was criticised for its alleged lack of novelty and mathematical rigor.
Other
There have been other criticisms as well which are less crucial than the above. One category is that Wolfram has bypassed entirely the usual scientific practice of critical review, i.e. he published his book before having had it reviewed by peers in the field. Less important is that Wolfram invents new terms for old concepts rather than using terminology already extant in the field.
Another category of criticism is that Wolfram comes close to making what many view as outrageous claims, such as that his work will make obsolete much of the existing scientific method and various mathematical methods. These are commonly characteristics of pathological science, protoscience, pseudoscience or crank science, though few if any critics have dared to call Wolfram a crank in prominent publications. Physicist Freeman Dyson has said of Wolfram's ANKOS, "There's a tradition of scientists approaching senility to come up with grand, improbable theories. Wolfram is unusual in that he's doing this in his 40s."
See also
 Controversial book
 Turingcomplete
 Emergence
 Scientific reductionism
 Stephen Wolfram
 Cellular automaton
 Matthew Cook
 List of books by title
External links
Official site
 Wolfram, Stephen, A New Kind of Science (http://www.wolframscience.com/nksonline). Wolfram Media, Inc., May 14, 2002. ISBN 1579550088
 Wolfram, Stephen, "Quick takes on some ideas and discoveries in A New Kind of Science (http://www.wolframscience.com/reference/quick_takes.html)". Wolfram Media, Inc.
 NKS 2004 conference (http://www.wolframscience.com/conference/2004/). Wolfram Media, Inc.
 InformationSpace (http://www.softcentral.com/informationspace/). Causal set exploration tool which supports 1 dimensional causal sets such as those found in NKS.
Reviews and Overviews
 Clark, Ed, Reviews (http://www.math.usf.edu/~eclark/ANKOS_reviews.html) (the most comprehensive collection of reviews of NKS)
 Amazon.com, book reviews (http://www.amazon.com/gp/product/customerreviews/1579550088/ref=cm_rev_sort/10319303547987028?customerreviews.sort_by=HelpfulVotes&me=ATVPDKIKX0DER&x=8&y=12) (ranked by votes)
 Schmidhuber, Juergen "A 35 year old kind of science" (http://www.idsia.ch/~juergen/wolfram.html) (with links to much earlier work on digital physics)
 Boguta, Kovas, "Comments on a review of NKS" (http://forum.wolframscience.com/showthread.php?s=b4dcb648c91f4096a166716339679de1&threadid=271) (an exposition of what NKS actually is, framed as a response to critics)
 Review and discussion of A New Kind of Science (http://books.slashdot.org/books/02/05/21/146210.shtml?tid=134). Slashdot.
 Krantz, Steven G., "Book review" (http://www.ams.org/bull/20034001/S0273097902009709/S0273097902009709.pdf). American Mathematical Society (PDF document)
 Rucker, Rudy, "Book Review" (http://sjsu.rudyrucker.com/%7Erudy.rucker/wolfram_review_AMM_11_2003.pdf). American Mathematical Monthly, November, 2003.
 Stephen Wolfram's lecture at MIT, "A New Kind of Science" (http://mitworld.mit.edu/play/147/) (Real Media video and audio, 1:36:36). Department of Mathematics at MIT, September 15, 2003.
 Naiditch, David, "Divine Secrets Of the YaYa Universe  Stephen Wolfram: A New Kind of Science—or a NotSoNew Kind of Computer Program?" (http://www.skeptic.com/wolfram.htm), Skeptic Magazine, issue 102, 2003.