The Book
Store
Downloads
Education
Archives
Forum
Now available for iPad
Download now »
Also available in the classic hardcover edition with art-quality printing »
(Restricted Access)
Register Now »
Jump to Page
Look Up in Index
Search
Preface
ix
1
The Foundations for a New Kind of Science
1
Section 1:
An Outline of Basic Ideas
1
Section 2:
Relations to Other Areas
7
Section 3:
Some Past Initiatives
12
Section 4:
The Personal Story of the Science in This Book
17
2
The Crucial Experiment
23
Section 1:
How Do Simple Programs Behave?
23
Section 2:
The Need for a New Intuition
39
Section 3:
Why These Discoveries Were Not Made Before
42
3
The World of Simple Programs
51
Section 1:
The Search for General Features
51
Section 2:
More Cellular Automata
53
Section 3:
Mobile Automata
71
Section 4:
Turing Machines
78
Section 5:
Substitution Systems
82
Section 6:
Sequential Substitution Systems
88
Section 7:
Tag Systems
93
Section 8:
Cyclic Tag Systems
95
Section 9:
Register Machines
97
Section 10:
Symbolic Systems
102
Section 11:
Some Conclusions
105
Section 12:
How the Discoveries in This Chapter Were Made
108
4
Systems Based on Numbers
115
Section 1:
The Notion of Numbers
115
Section 2:
Elementary Arithmetic
117
Section 3:
Recursive Sequences
128
Section 4:
The Sequence of Primes
132
Section 5:
Mathematical Constants
136
Section 6:
Mathematical Functions
145
Section 7:
Iterated Maps and the Chaos Phenomenon
149
Section 8:
Continuous Cellular Automata
155
Section 9:
Partial Differential Equations
161
Section 10:
Continuous Versus Discrete Systems
167
5
Two Dimensions and Beyond
169
Section 1:
Introduction
169
Section 2:
Cellular Automata
170
Section 3:
Turing Machines
184
Section 4:
Substitution Systems and Fractals
187
Section 5:
Network Systems
193
Section 6:
Multiway Systems
204
Section 7:
Systems Based on Constraints
210
6
Starting from Randomness
223
Section 1:
The Emergence of Order
223
Section 2:
Four Classes of Behavior
231
Section 3:
Sensitivity to Initial Conditions
250
Section 4:
Systems of Limited Size and Class 2 Behavior
255
Section 5:
Randomness in Class 3 Systems
261
Section 6:
Special Initial Conditions
266
Section 7:
The Notion of Attractors
275
Section 8:
Structures in Class 4 Systems
281
7
Mechanisms in Programs and Nature
297
Section 1:
Universality of Behavior
297
Section 2:
Three Mechanisms for Randomness
299
Section 3:
Randomness from the Environment
301
Section 4:
Chaos Theory and Randomness from Initial Conditions
304
Section 5:
The Intrinsic Generation of Randomness
315
Section 6:
The Phenomenon of Continuity
327
Section 7:
Origins of Discreteness
337
Section 8:
The Problem of Satisfying Constraints
342
Section 9:
Origins of Simple Behavior
351
8
Implications for Everyday Systems
363
Section 1:
Issues of Modelling
363
Section 2:
The Growth of Crystals
369
Section 3:
The Breaking of Materials
374
Section 4:
Fluid Flow
376
Section 5:
Fundamental Issues in Biology
383
Section 6:
Growth of Plants and Animals
400
Section 7:
Biological Pigmentation Patterns
422
Section 8:
Financial Systems
429
9
Fundamental Physics
433
Section 1:
The Problems of Physics
433
Section 2:
The Notion of Reversibility
435
Section 3:
Irreversibility and the Second Law of Thermodynamics
441
Section 4:
Conserved Quantities and Continuum Phenomena
458
Section 5:
Ultimate Models for the Universe
465
Section 6:
The Nature of Space
472
Section 7:
Space as a Network
475
Section 8:
The Relationship of Space and Time
481
Section 9:
Time and Causal Networks
486
Section 10:
The Sequencing of Events in the Universe
497
Section 11:
Uniqueness and Branching in Time
504
Section 12:
Evolution of Networks
508
Section 13:
Space, Time and Relativity
516
Section 14:
Elementary Particles
525
Section 15:
The Phenomenon of Gravity
530
Section 16:
Quantum Phenomena
537
10
Processes of Perception and Analysis
547
Section 1:
Introduction
547
Section 2:
What Perception and Analysis Do
548
Section 3:
Defining the Notion of Randomness
552
Section 4:
Defining Complexity
557
Section 5:
Data Compression
560
Section 6:
Irreversible Data Compression
572
Section 7:
Visual Perception
577
Section 8:
Auditory Perception
585
Section 9:
Statistical Analysis
588
Section 10:
Cryptography and Cryptanalysis
598
Section 11:
Traditional Mathematics and Mathematical Formulas
606
Section 12:
Human Thinking
620
Section 13:
Higher Forms of Perception and Analysis
632
11
The Notion of Computation
637
Section 1:
Computation as a Framework
637
Section 2:
Computations in Cellular Automata
638
Section 3:
The Phenomenon of Universality
642
Section 4:
A Universal Cellular Automaton
644
Section 5:
Emulating Other Systems with Cellular Automata
656
Section 6:
Emulating Cellular Automata with Other Systems
664
Section 7:
Implications of Universality
674
Section 8:
The Rule 110 Cellular Automaton
675
Section 9:
The Significance of Universality in Rule 110
690
Section 10:
Class 4 Behavior and Universality
691
Section 11:
The Threshold of Universality in Cellular Automata
694
Section 12:
Universality in Turing Machines and Other Systems
706
12
The Principle of Computational Equivalence
715
Section 1:
Basic Framework
715
Section 2:
Outline of the Principle
716
Section 3:
The Content of the Principle
719
Section 4:
The Validity of the Principle
726
Section 5:
Explaining the Phenomenon of Complexity
735
Section 6:
Computational Irreducibility
737
Section 7:
The Phenomenon of Free Will
750
Section 8:
Undecidability and Intractability
753
Section 9:
Implications for Mathematics and Its Foundations
772
Section 10:
Intelligence in the Universe
822
Section 11:
Implications for Technology
840
Section 12:
Historical Perspectives
844
Notes
849
General Notes
849
Notes 1:
The Foundations for a New Kind of Science
859
Notes 2:
The Crucial Experiment
865
Notes 3:
The World of Simple Programs
883
Notes 4:
Systems Based on Numbers
901
Notes 5:
Two Dimensions and Beyond
927
Notes 6:
Starting from Randomness
947
Notes 7:
Mechanisms in Programs and Nature
967
Notes 8:
Implications for Everyday Systems
991
Notes 9:
Fundamental Physics
1017
Notes 10:
Processes of Perception and Analysis
1067
Notes 11:
The Notion of Computation
1107
Notes 12:
The Principle of Computational Equivalence
1125
Index
Copyright Page
Colophon
Front Cover
Back Cover
NKS|Online FAQs
Notes from the Book
The complete notes section from the book reformatted with larger text size.
Buy Online »
Commemorative Poster
The complete text of
A New Kind of Science
on a 26" x 40" poster.
Buy Online »