# Index

TMs

see Turing machines

Toda lattice

as exactly soluble, 1133

Toes (animal)

formation of, 419

`ToExpression`

and parsing, 1103

Toffoli, Tommaso (Italy/USA, 1943– )

and 2D CA simulators, 928

and 2D cellular automata, 880

in Preface, xiii

Tokens

in formal languages, 1103

Tones

in music, 1079

Tongue

human, 1105

Tool use

and defining intelligence, 1178

Toom, Andrei (Russia/USA, 1942– )

and transitions in CAs, 981

Top (spinning)

as exactly soluble, 1133

Topochronology, 1027

Topography

and identifying artifacts, 1184

origins of, 1001

and weather, 1177

Topological defects, 1045

and localized structures, 990

Topological dimension, 1030

Topological entropy, 958, 959

computing, 1084

history of, 961

Topological equivalence

and reversible CAs, 961

Topological field theories

and defining dimension, 1031

and quantum computers, 1148

and spin networks, 1055

Topological indices

and chemical properties, 1195

Topological processes (T1 and T2)

in planar networks, 1038

Topological spacetime entropy, 960

Topological structure

and visual memory, 624

Topology

axioms for, 774, 1155

and biological form, 1004

and cellular automata, 930

and discrete space, 1050

and general relativity, 1052

of networks, 1045

and networks from continuous systems, 1031

of Schwarzschild solution, 1053

and texture perception, 1076

Topos theory

as idealization of math, 1150

Toppling

in sandpile model, 989

Torsion

in general relativity, 1052

in unified field theory, 1028

Tortoiseshell cats

patterns on, 1014

Tossing (of coins, etc.)

as source of randomness, 305, 968, 970

`ToString`

and bracket sequences, 897

Total functions

primitive recursive as, 907

in Turing machines, 1143

Total recursive functions

see Primitive recursive functions

Totalistic cellular automata, 60

2D, 170

and `CellularAutomaton`

, 867

implementation of, 886

as not reversible, 1017

number of, 886

and pigmentation patterns, 1012

with random initial conditions, 233

universality in, 693, 1117

and visual feature extraction, 1077

Totient

see `EulerPhi`

Tournaments

of game programs, 1104

Towers of Hanoi puzzle, 893

Towns

see Cities

Toys

complex motion in, 1183

random motion in, 968

Tracery

in Gothic windows, 873

Tracks

made by turning vehicles, 418

Trading

effects of details of, 1015

with extraterrestrials, 1191

processes of, 430

Traffic flow

*1/f* noise in, 969

instabilities in road, 1014

Training

of animals, 825

and responses to events, 827

Trains of thought

and free will, 752

Transcendental equations

numbers defined by, 916

undecidability in, 1138

universality in, 731

Transcendental numbers, 912

constructed from digits, 914

continued fractions of, 144

digit sequences of, 136, 142

and Egyptian fractions, 915

as precursors to my work, 878

see also π, , etc.

Transfer matrices, 983

Transfinite hierarchy of formalisms, 1159

Transfinite induction, 1160

and Goodstein sequences, 1163

in set theory, 1154

Transfinite numbers, 1162

and abstraction in math, 792, 860, 1149

as generalizing numbers, 1168

Transformation rules

and axioms, 1150

examples of in Mathematica, 854

in Mathematica, 627, 1103

in symbolic systems, 102

Transients

in class 4 systems, 282

in code 20 cellular automaton, 964

in Game of Life, 965

in halting register machines, 896

and irreversibility in rule 37R, 454

for mobile automata, 887

in state transition graphs, 961

in three-body problem, 973

and undecidability, 754

Transistors

and `Nand`

, 1173

Transitions

in class 4 systems, 948

in continuous CAs, 244, 948

see also Phase transitions

Transitivity

and confluence property, 1036

Translations

between languages, 1086

between math systems, 816

of functions in logic, 807

see also Emulation

Transmutation

in alchemy, 861

Transponders

and radio signals, 1188

`Transpose`

and Ricci from Riemann tensor, 1049

Transposition sort, 1142

Trapezoidal primes, 911

Travelling salesman problem, 985, 1145

Tree

backtracking, 1089

Tree-like patterns

in 2D cellular automata, 171

in 2D substitution systems, 188

in crystals, 371

in rule 184, 359

see also Nesting

Tree networks

as having infinite dimension, 480

Trees

for address decoding on chips, 1183

alkane molecules as, 1194

as alternative to hashing, 1100

in animal branching structures, 1008

and attractor structure, 959

balanced binary, 897, 898

binary

see Binary trees

as combinator expressions, 1123

for computation of powers, 615

depth of in expressions, 897

and digit sequences, 891

dynamic, 936

evolving in symbolic systems, 897

expressions as, 897

in Huffman coding, 1071

in landscape structures, 1001

Mathematica expressions as, 989

`Nand`

, 1096, 1157

networks forming, 196

as origins of nesting, 357

parse, 1103

random, 1084

in recursive evaluation, 907

for representing integers, 916

space of possible, 405

in state transition graphs, 961

and structure of proofs, 1155

and substitution systems, 84

in transition graphs for additive rules, 963

and understanding expressions, 1177

Trees (botanical)

and Descartes on complexity, 861

forms of, 401

growth of, 1004

Trend-based weather prediction, 1178

Triangle inequality

and definition of distance, 1030

Triangles

in discrete space, 1051

Lagrange points forming, 972

in ornamental art, 873

produced by cellular automaton evolution, 24, 225, 947

produced in rule 30, 28

Triangular lattice

cellular automata on, 930

percolation theory on, 983

random walks on, 329

Triangular waveform, 917

Triangulation

in GPS, 1086

and quantum gravity, 1054

of space, 533, 1050

Tributaries

building up rivers from, 359, 1001

`TrigFactor`

and sine curves, 917

Triggerfish

pigmentation pattern of, 426

Trigonometric equations

universality in, 731, 1129

Trigonometric functions

and shapes of leaves, 1006

and undecidability, 1138

Trigonometric series

machine for computing, 1107

nested functions from, 918

and origin of set theory, 1154

and spectra of nested sequences, 1081

Trigonometric sum formulas

of Ramanujan, 911

Trillion (as 1,000,000,000,000), 849

Trillions of rules

in finding doubling CAs, 832

Trilobites

as examples of evolution, 1003

regularities in, 385

Trinomial coefficients, 1091

and rule 150 pattern, 611

Tripling cellular automata, 1186

Trisection of angles, 1137

Tritone (musical interval), 146, 917

Trivalent networks

see Networks

Troy

maze as logo for, 873

Truchet, Sébastien (Jean) (France, 1657–1729)

and patterns from rules, 875

`True`

defined with `Or`

and `Not`

, 817

`Nand`

statements equivalent to, 781

True but unprovable statements, 1167

`TrueQ`

and truth values, 1158

Truncated icosahedron

and spherical networks, 1049

Truncated octahedron

and 3D lattices, 930

Trusses

characteristic shapes of, 1183

Truth

and computational irreducibility, 1196

and essential incompleteness, 1159

and incompleteness, 1167

in math reached only by experiment, 899

and theories of communication, 1181

and undecidability, 1136, 1139

Truth tables, 1170

vs. axioms, 802

in multiway systems, 1173

and satisfiability, 768

Truth values

intermediate, 1175

and lack thereof, 1158

Tubes

formation of inside animals, 417

in musical instruments, 1079

Tulip bulbs

and speculative markets, 1015

Tumbling of microorganisms, 970

Tumor growth, 1011

aggregation system for, 978

Tuning

musical, 917

Tunnelling

as basic quantum effect, 1059

Turaev–Viro invariants, 1055

Turbulence, 376

as analogy for quantum field theory, 1059, 1061

in atmosphere, 1001

in convection, 1000

in flow of sand, 1001

vs. fracture roughness, 994

in gravitational fields, 1053

and history of complexity, 862

and history of randomness, 968

in interstellar medium, 1188

as motivating question, 17

numerical computation of, 924, 996

in QCD field configurations, 1061

and snowflake differences, 992

sound of, 1079

as source of apparent intelligence, 837

traditional models of, 997

in two dimensions, 999

Turing, Alan M. (England, 1912–1954)

and animal pigmentation, 1012

and artificial intelligence, 1099

and computable numbers, 1128, 1137

computer programs of, 1013

and continuous computation, 1128

and defining computability, 1125

and diagonal arguments, 1128

and history of computers, 1107

and oracles, 1126

and origins of universality, 1110

and reaction-diffusion, 1012

and theoretical biology, 879, 1004

and Turing machines, 879, 889

and undecidability, 1136

and undecidability of word problem, 1141

and universal TM, 1119

Turing completeness

see Universality (computational)

Turing degrees (arithmetic hierarchy), 1139

Turing machines, 78–81

2D, 184–186

attitude of Gödel towards, 1159

attractors in, 961

axiom systems for, 1167

and Church's Thesis, 1125

compared to circuits, 1148

and computable reals, 1128

computing increment, 758

emulated by CAs, 658, 1111

emulated by combinators, 1122

emulated by Life, 1117

emulated by recursive functions, 1121

emulated by register machines, 671, 1114

emulated by satisfiability, 1146

emulated by tag systems, 670, 1114

emulating CAs, 665, 765, 1113

emulating more colors, 669, 1113, 1119

emulating multiway systems, 765

emulating rule 60, 1119

emulating rule 110, 707, 1119

emulating substitution systems, 765

enumeration of, 1120

evolution of as P computation, 1142

functions computed by small, 1143, 1144

and growth rates of functions, 1163

growth rates of running times, 1145

halting of one-way, 759

halting probabilities for, 1143

halting problem for, 1137

history of, 889

history of 2D, 930

and history of CAs, 876

history of universal, 1119

and history of universality, 1110

as idealization of math, 1150

implementation of, 888

implementation of 2D, 930

implementation of non-deterministic, 1146

initial conditions for, 710

localized structures in, 888

longest halting times for, 1144

non-deterministic, 766, 939

number of, 888

one-way, 759

and oracles, 1126

and P completeness, 1149

paths in 3D from 2D, 931

as precursors to my work, 879

quantum analogs of, 1147

random initial conditions in, 949

and recursive sets, 1138

with rule 60-like behavior, 1120

running times of, 761, 1143

and second-order logic, 1167

simplest with complex behavior, 708–709, 1120

small for elementary rules, 1113

state-color tradeoffs in, 888, 1120

symmetries of, 1120

and time in universe, 486

undecidability in, 1136

and universal CAs, 1115

universality in simple, 706–711

and word problem in groups, 1141

Turing test (in AI), 1099, 1178

Turmites (2D Turing machines), 930

Turning machines (2D Turing machines), 930

Turns

and substitution system paths, 892

Turtles

pigmentation patterns of, 426

Turtles (artificial)

and 2D Turing machines, 930

and 3D paths, 931

Tweeks (natural radio), 1187

Twin paradox

time dilation in, 524

Twin primes, 909

unsolved problem of, 1166

Twinning

in crystal growth, 993

Twins

biometrics of, 1014

Twistor formulation of general relativity, 1048

Twitching in muscles

and free will, 1136

Two-body problem, 313, 972

and computational reducibility, 737

as exactly soluble, 1133

in general relativity, 1053

Two-cell neighborhood cellular automata, 885

Two-dimensional

cellular automata, 170–181

constraints, 211

data compression, 568

mobile automata, 931

networks, 195

random walks, 329

substitution systems, 187–192

systems in general, 169–221

template numbering, 941

Turing machines, 184–186

wave equation, 923

Two's complement number representation, 902, 942

Tycho (crater)

circular shape of, 1187

Tylor, Edward B. (England, 1832–1917)

and animism, 1195

Type theory

and category theory, 1154

Types

of functions and data, 898