# Index

Object-oriented programming, 867

Object recognition, 624

Objects

described by axiom systems, 797

and image compression, 1074

Observables

in quantum mechanics, 1056

Observational errors

and Gaussian distribution, 977

and origin of randomness, 967

Observers

and Anthropic Principle, 1026

computational abilities of, 737

definition of particles for, 1062

and origin of causal networks, 487

Occam's razor, 1025

Ocean currents

and weather, 1177

Ocean waves, 1001

as example of randomness, 301

nested breaking of, 997

pattern formation in, 947

repetitive behavior in, 988

Oceans

exploration of, 1191

finding artifacts under, 1183

whale songs in, 1180

Ocelot

pigmentation pattern of, 426

OCR (optical character recognition)

and cellular automata, 877

Octahedra

extraterrestrial in 2001, 1190

truncated, 930, 987

Octanes, 1194

Octonions

as generalizing numbers, 1168

Octopus

communication by, 1181

form of tentacles of, 385

visual system of, 1075

Ocular dominance stripes

CA model for, 1012

maze-like patterns in, 1013

in visual system, 1075

OddQ (test for odd numbers)

and nested patterns, 931

and rule 132, 638

Odds and Evens game, 1105

ODEs, 922

see also Ordinary differential equations

Odlyzko, Andrew M. (USA, 1949– )

and additive CAs, 951

as coauthor of paper, 881

in Preface, xiii

and zeros of zeta function, 918

Odometer

and history of computing, 1107

Odor perception, 1105

and experience of dogs, 827

Offset lists

in general cellular automata, 927

OH (hydroxyl) frequency, 1189

Oil and water

separation of, 980

Oil fires

patterns in, 377

visible from space, 1187

Olaus Magnus (Sweden/Italy, 1490–1568)

and snowflakes, 992

Olbers' paradox, 1021

Old English

logic operations in, 1173

Olfactory perception, 1105

and experience of dogs, 827

Olive shell

growth of, 415

Omega (halting probability), 1067

omega (first transfinite ordinal), 1162

One-sided additivity

and cryptography, 1088

repetition from, 954

One-time pad (in cryptography), 1086

One-to-one mapping (injective), 960

Ones

expressing numbers with, 916

number of (DigitCount), 902

Onsager, Lars (USA, 1903–1976)

and 2D Ising model, 982

Onto cellular automata, 280, 959

Ontology

implications for, 1197

and notions of space, 1028

Opcodes

in practical computers, 1108

in register machines, 896

Open sets

and axioms of topology, 1155

Open systems

and thermodynamics, 455

Operating systems

and concept of halting, 1137

and history of computing, 1108

in practical computers, 1108

Operation counts in computations, 1143

Operator representations

for integers, 916

Operator systems, 801

automated proofs in, 1158

evolution rules for, 898

frameworks for proofs in, 1177

vs. multiway systems, 1169

Operators

as generalizing numbers, 1168

notation for, 1182

possible Boolean, 806

precedence of, 1104

precedence of in math, 1150

in quantum theory, 1056

Optic nerve, 1075

Optical amplifier, 310

Optical character recognition (OCR)

and history of CAs, 877

Optical computing

CA implemented with, 869

and quantum computers, 1148

Optical fibers

as technology component, 1195

Optical illusions, 1076

Optical SETI, 1189

Optics

and history of math in science, 859

path integral in, 1061

Optimal algorithms, 1141

Optimal evaluation chains, 1095

Optimality

and defining purpose, 829

and models of markets, 1015

Optimization

combinatorial, 985

and complexity in biology, 398

of designs in engineering, 1193

intuition about in programs, 872

and Occam's razor, 1025

in plant leaf arrangements, 408

Optimized circuit blocks, 1193

Optimizers

and proofs about programs, 1168

search strategies in, 1193

Options

market prices of, 1015

Or

axioms in terms of, 1151

and Boolean formulas, 1095

calculus of expressions, 1170

emulated by CAs, 662, 1112

encoded as integer equation, 1160

in multivalued logic, 1175

and P completeness, 1149

and satisfiability, 1146

table for, 806

theorems involving, 817

words in languages for, 1173

Oracles (in computation theory), 1126

and arithmetic hierarchy, 1139

based on infinite tables, 720

and intermediate degrees, 1131

and non-standard arithmetic, 1169

and second-order logic, 1167

Orbits

in Bohr atom, 1056

of comets and Gaussians, 977

and history of computing, 1107

randomness in, 313

as simple shapes, 1187

in three-body problem, 972

Order

emergence from randomness, 223

Order diagrams of posets

and causal networks, 1040

Order of updates

in sequential CAs, 1034

in sequential substitution systems, 894

in string rewriting, 497

in symbolic systems, 898

see also Causal invariance

Order parameters

in phase transitions, 981

Ordered fields

axioms for, 1153

Orderless (commutative)

and associative CAs, 956

Boolean functions, 1173

and generalized additivity, 952

and speedups in evolution, 1095

Orders of infinity, 1127, 1162

Ordinal numbers

and encoding of proofs, 1163

as generalizing numbers, 1168

and notions of infinity, 1162

Ordinary differential equations (ODEs), 922

for chemical processes, 1013

Oresme, Nicole (France, ~1320–1382)

and time as a dimension, 1031

Organic molecules

production of, 1179

Organization

see Self-organization

Organizational structures

and history of complexity, 862

and Occam's razor, 1025

Organogenesis in plants, 409

Organs

and biological evolution, 389, 1002

separate rules for different, 383

Origami (paperfolding)

NP completeness in, 1145

rules in, 875

Origin of Species, 1001

Ornament

examples of, 43

grammatical rules in, 1181

and notion of purpose, 830

rules in, 872

and theory of form, 967

Orreries, 1184

Orthogonal bases, 1072

and image compression, 573

and radio signals, 1188

Oscillations

in chemical reactions, 1013

of density in rule 73, 954

in fluid flow, 998

in math functions, 917, 1134

origins of, 354-356

in PDEs, 988

Oscillators

in Game of Life, 964

nonlinear, 971

in quantum history, 1056

Oseen, C. William (Sweden, 1879–1944)

and fluid flow past spheres, 998

Oster, George F. (USA, 1940– )

and patterns on shells, 1012

in Preface, xiii

Other minds

problem of recognizing, 1197

Otter (theorem-proving system), 1158

Outer

and branching patterns, 1005

and enumerating expressions, 897

and metrics on surfaces, 1048

and shape tensors, 980

Outer totalistic rules

in cellular automata, 928

Outlying data, 1083

Overlaps

in networks, 510

in strings, 503, 1033

Overshooting

in gradient descent, 985

Ozsváth-Schücking rotating vacuum, 1053