auto
small
medium
large
x-large
Notes
Chapter 12
Section 2
auto
small
medium
large
x-large
Preface
1
The Foundations for a New Kind of Science
1
An Outline of Basic Ideas
2
Relations to Other Areas
3
Some Past Initiatives
4
The Personal Story of the Science in This Book
2
The Crucial Experiment
1
How Do Simple Programs Behave?
2
The Need for a New Intuition
3
Why These Discoveries Were Not Made Before
3
The World of Simple Programs
1
The Search for General Features
2
More Cellular Automata
3
Mobile Automata
4
Turing Machines
5
Substitution Systems
6
Sequential Substitution Systems
7
Tag Systems
8
Cyclic Tag Systems
9
Register Machines
10
Symbolic Systems
11
Some Conclusions
12
How the Discoveries in This Chapter Were Made
4
Systems Based on Numbers
1
The Notion of Numbers
2
Elementary Arithmetic
3
Recursive Sequences
4
The Sequence of Primes
5
Mathematical Constants
6
Mathematical Functions
7
Iterated Maps and the Chaos Phenomenon
8
Continuous Cellular Automata
9
Partial Differential Equations
10
Continuous Versus Discrete Systems
5
Two Dimensions and Beyond
1
Introduction
2
Cellular Automata
3
Turing Machines
4
Substitution Systems and Fractals
5
Network Systems
6
Multiway Systems
7
Systems Based on Constraints
6
Starting from Randomness
1
The Emergence of Order
2
Four Classes of Behavior
3
Sensitivity to Initial Conditions
4
Systems of Limited Size and Class 2 Behavior
5
Randomness in Class 3 Systems
6
Special Initial Conditions
7
The Notion of Attractors
8
Structures in Class 4 Systems
7
Mechanisms in Programs and Nature
1
Universality of Behavior
2
Three Mechanisms for Randomness
3
Randomness from the Environment
4
Chaos Theory and Randomness from Initial Conditions
5
The Intrinsic Generation of Randomness
6
The Phenomenon of Continuity
7
Origins of Discreteness
8
The Problem of Satisfying Constraints
9
Origins of Simple Behavior
8
Implications for Everyday Systems
1
Issues of Modelling
2
The Growth of Crystals
3
The Breaking of Materials
4
Fluid Flow
5
Fundamental Issues in Biology
6
Growth of Plants and Animals
7
Biological Pigmentation Patterns
8
Financial Systems
9
Fundamental Physics
1
The Problems of Physics
2
The Notion of Reversibility
3
Irreversibility and the Second Law of Thermodynamics
4
Conserved Quantities and Continuum Phenomena
5
Ultimate Models for the Universe
6
The Nature of Space
7
Space as a Network
8
The Relationship of Space and Time
9
Time and Causal Networks
10
The Sequencing of Events in the Universe
11
Uniqueness and Branching in Time
12
Evolution of Networks
13
Space, Time and Relativity
14
Elementary Particles
15
The Phenomenon of Gravity
16
Quantum Phenomena
10
Processes of Perception and Analysis
1
Introduction
2
What Perception and Analysis Do
3
Defining the Notion of Randomness
4
Defining Complexity
5
Data Compression
6
Irreversible Data Compression
7
Visual Perception
8
Auditory Perception
9
Statistical Analysis
10
Cryptography and Cryptanalysis
11
Traditional Mathematics and Mathematical Formulas
12
Human Thinking
13
Higher Forms of Perception and Analysis
11
The Notion of Computation
1
Computation as a Framework
2
Computations in Cellular Automata
3
The Phenomenon of Universality
4
A Universal Cellular Automaton
5
Emulating Other Systems with Cellular Automata
6
Emulating Cellular Automata with Other Systems
7
Implications of Universality
8
The Rule 110 Cellular Automaton
9
The Significance of Universality in Rule 110
10
Class 4 Behavior and Universality
11
The Threshold of Universality in Cellular Automata
12
Universality in Turing Machines and Other Systems
12
The Principle of Computational Equivalence
1
Basic Framework
2
Outline of the Principle
3
The Content of the Principle
4
The Validity of the Principle
5
Explaining the Phenomenon of Complexity
6
Computational Irreducibility
7
The Phenomenon of Free Will
8
Undecidability and Intractability
9
Implications for Mathematics and Its Foundations
10
Intelligence in the Universe
11
Implications for Technology
12
Historical Perspectives
Notes
Look up in index
Text search
Jump to page
‹
›
Notes
Chapter 12:
The Principle of Computational Equivalence
Section 2:
Outline of the Principle
[History of] Church's Thesis
History [of PCE]
Note for mathematicians [about PCE]
![[History of] Church's Thesis](/nks/notes/notes-12-2--history-of-churchs-thesis/thumb.png "[History of] Church's Thesis")
![History [of PCE]](/nks/notes/notes-12-2--history-of-pce/thumb.png "History [of PCE]")
![Note for mathematicians [about PCE]](/nks/notes/notes-12-2--note-for-mathematicians-about-pce/thumb.png "Note for mathematicians [about PCE]")