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