# Index

T violation (time reversal violation), 1019

T1 and T2 processes in networks, 1038

Table

basic examples of, 853

Tables

for Boolean formulas, 1095

leading digits in, 914

of primes, 910

of random numbers, 968

see also Multiplication tables

Tabulating machines, 1107

Taffy

as chaos theory example, 306

fracture in, 994

Tag systems, 93-94

cyclic, 95

see also Cyclic tag systems

density in, 894

emulated by correspondence systems, 1140

emulated by recursive functions, 1121

emulated by universal TM, 706, 1119

emulating CAs, 667, 1113

emulating TMs, 670, 1114

implementation of, 894

multiway, 1141

one-element-dependence, 1114

as precursors to my work, 879

random initial conditions in, 949

and TM 596440, 1120

undecidability in, 1136

uniform, 82

see also Substitution systems

universality in simple, 1120

universality of one-element dependence, 1120

Tail recursion

and recursive functions, 907

Tails (of data), 1083

Taj Mahal

nesting in gardens of, 874

Take (take elements)

basic example of, 853

Tally sticks

and application of randomness, 968

Tan

curve of, 145

Tang, Chao (USA, 1958– )

and self-organized criticality, 989

Tangencies

in circle packings, 986

in ornamental art, 873

Tanh

in neural network models, 1102

and solving Ising model, 982

Taoism, 1196

Tape

of Turing machine, 78

Tapir

pigmentation pattern of, 426

Taps in shift registers, 975

Tarski, Alfred (Poland/USA, 1902–1983)

and axioms for geometry, 1154

and axioms for groups, 1153

and axioms for predicate logic, 1152

and real algebra, 1154

and undecidability of group theory, 1159

Taste

sense of, 1105

Tate-Shafarevich group, 1164

Tau lepton

mass of, 1046

as type of particle, 1043

Tautologies

based on Nand, 781, 1157

Tautology

laws of, 817

Tea leaves, 968

Tearing of materials, 995

Technical analysis

of financial markets, 1015

Technology

components used in, 1195

dating of jargon about, 849

discussions of in this book, 1192

future of, 832

history of vs. fossil record, 398

and human condition, 846

implications for, 840-843

new purposes for, 843

and Occam's razor, 1025

optimization in advanced, 829

search-based development of, 1193

as stimulus for basic science, 42

summary of relations to, 11, 863

TECO (text editor), 894

Tectonic activity, 1001

Teeth

folding in formation of, 417

patterns in ray and shark, 1007

Teichmüller spaces (parameter spaces), 1006

Telegraphy

and data compression, 1069

and SETI, 1189

Teleology, 1185

and argument by design, 861

and biological evolution, 387

Telepathy

as feature of extraterrestrials, 1190

Telephone

bandwidth of, 1079

development of, 1080

and sound compression, 1072

Telephone information services, 1100

Telephone networks

Monte Carlo studies of, 1192

Teleportation, 1058

Telescopes

as analogy, 42

and SETI, 835

Television

bandwidth of, 1079

data compression for, 1072

as source of radio signals, 1188

Telos (final cause), 1185

Temperament (in music), 917, 1079

Temperature

of black holes, 1062

as characterizing equilibrium, 450

in crystal growth, 993

differences in convection, 1000

in Ising model, 982

repeatable randomness in, 976

and weather, 1177

Templates

for 2D constraints, 941

in aggregation systems, 978

and hash codes in neural networks, 624

in tilings, 213

in visual perception, 579

Temporal logics

and causal invariance, 1035

Temporal sequences

in cellular automata, 960

TensorRank

and tensors in differential geometry, 1049

Tensors

characterizing symmetry of pattern, 980

in differential geometry, 1049

duals of, 1050

Einstein equations and, 1052

manipulation of, 1048

norms of, 1050

Tent map, 150

exact iterates of, 919

and history of chaos theory, 971

Tent olive shell

pattern on, 423

Tent patterns on shells, 423

Tentacles

of octopus, 385

and spines on shells, 1008

Term rewrite systems

see Multiway systems

Termination

of function computations, 1163

in multiway systems, 1036

problems

see Halting problems

in symbolic systems, 897

Termite structures

and aggregation systems, 1011

as animal artifacts, 1184

Ternary

binary-coded, 1070

Ternary cellular automata, 60

Ternary logic, 814

Ternary operators, 1171

Terraces in crystals (hoppering), 993

Territories

defending and bird songs, 1180

and Voronoi diagrams, 987

Tertiary structure (of proteins), 1003, 1184

Terza rima

and rules for poetry, 875

Tesla, Nikola (USA, 1856–1943)

and SETI, 1188, 1189

Tessellation automata

see Cellular automata

Tessellations

defined by constraints, 213

of fixed blocks, 582

Tests of models, 364

Tests of randomness, 1084

for digit sequences, 912

for rule 30, 871

Tetrad formulation of general relativity, 1048

Tetradecahedron, 930, 987, 988

Tetrahedral group (A_4)

with trivalent Cayley graph, 1032

Tetrahedron

as cluster shape in sphere packings, 986

network as net of, 476

network transformed to cube, 1038

as rigid 3D structure, 1031

in spin networks, 1055

as tip of plant stem, 1004

Tetrakaidecahedron

see Tetradecahedron

Tetration

and Ackermann function, 906

and halting in symbolic systems, 897

and symbolic systems, 897

Text

compression of, 1084

in databases, 621

in practical computers, 1108

redundancy of, 1086

Text-based interfaces, 1102

Textbooks

and computational irreducibility, 1133

of computer science and Church's Thesis, 1126

math in, 773

Textile cone shell

pattern on, 423

Textile making

rules in, 874

Textons

and texture perception, 1076

Texture perception, 577

history of, 1076

Textures

in biology, 387

generating, 841, 1078

of physical surfaces, 1077

Texturing

use of randomness in, 1192

Thallus

shape of, 385

Theism, 1195

Theology

and complexity, 3, 861

and form of extraterrestrials, 1191

and free will, 1135

and issues of modelling, 991

and teleology, 1185

and ultimate theory of physics, 1025

and uniqueness of life on Earth, 1180

and universe as intelligent, 1195

see also God

see also Religion

Theophrastus (Greece, ~371 – ~287 BC)

and shapes of leaves, 1005

Theorems, 779

automated proving of, 1157

see also Automated theorem proving

character of different types, 820

vs. computer experiments, 899

and definition of math, 860

distributions of in fields of math, 1175

general characterizations of, 1176

interesting ones in logic, 816

involving Nand, 818, 1175

in operator systems, 801

pattern of in logic, 812

pattern of in simple axiom systems, 812

of shortest axioms for logic, 811

Theoretical biology

and complexity, 861

history of, 1003

undecidability in, 1138

Theoretical science

and computational reducibility, 749

traditional methods of, 737

Theory of being (ontology)

implications for, 1197

Theory of biology

possibilities for a, 397

Theory of computation, 753

Theory of everything, 1025

Theory of knowledge (epistemology)

implications for, 1196

Theory of structures

in mathematics, 1150

Theory of universe

see Ultimate theory of physics

Thermal diffusion

and randomization times, 970

Thermal equilibrium

in early universe, 1055

and Ising model, 982

see also Equilibrium

Thermal noise, 968

in microprocessors, 970

Thermal perception, 1105

Thermodynamic formalism (for dynamical systems), 959

Thermodynamic limit

for diffusion equation, 1024

and phase transitions, 983

Thermodynamics

analogies to computation, 726

vs. biological evolution, 1003

of computation, 1020

and crystal growth, 993

and defining life, 824, 1178

history of, 1019

and history of complexity, 862

Second Law of, 441-457

see also Second Law of Thermodynamics

vs. strange attractors, 1020

summary of relations to, 16

Theta functions

see EllipticTheta

Thinking

attributed to universe, 1195

communication and, 1181

emulation by computers of, 733

and foundations of math, 1176

and Gödel's Theorem, 1159

in higher math, 1177

history of studying, 1099

human, 620-631

influence of language on, 1181

logic as representation of, 860

machines, 628

and Principle of Computational Equivalence, 733

and ultimate theory of universe, 465

Thinking Machines Corporation, xiii, 881

Thirteenth problem (of Hilbert), 1128

Thom, René F. (France, 1923-[2002])

in Preface, xiii

and structure in animals, 1009

and theoretical biology, 1004

Thompson, D'Arcy W. (Scotland, 1860–1948)

and forms in nature, 967

and growth processes, 1010

and leaf shapes, 1006

and theoretical biology, 1004

Thomson, William

see Kelvin

Threads between particles, 544

Three-body problem, 972

and computational irreducibility, 1132

and history of chaos, 971

and history of complexity, 862, 1068

as precursor to my work, 879

randomness in, 314

and undecidability, 1138

Three-dimensional

cellular automata, 182-183

networks, 195, 1030

wave equation, 923

Three squares problem, 910

Through

and recursive functions, 907

Throw

and context-free parsing, 1103

and pointer-based encoding, 1071

and testing invariances, 1022

and testing reversibility, 1017

Thue, Axel (Norway, 1863–1922)

and circle packings, 985

and Diophantine equations, 1164

and multiway systems, 938

and repetition-free sequences, 944

and substitution systems, 879, 893

and word problem for semigroups, 1141

Thue equations, 1164

Thue-Morse sequence, 890

atomic layers in, 1082

as cube-free sequence, 944

and cyclic tag systems, 895

generating function for, 1092

and period-doubling sequence, 892

represented by special functions, 1092

rule 60 applied to, 1091

simplest CA generating, 1186

spectrum of, 586, 1081

statistics of blocks in, 594

from substitution system, 83

and Walsh functions, 1073

Thunderstorms

1/f noise in, 969

Thwaites conjecture (3n+1 problem), 904

Tic-tac-toe

network for, 939

Tidal forces

and Einstein equations, 1052

Tides

machine for predicting, 1107

TIFF format

compression in, 1070

Tiger

pigmentation pattern of, 426

Tilings, 211-221

from 2 x 2 squares, 1078

and aggregation systems, 979

approximate solutions of, 345

and cellular automata, 943, 1139

as cellular automaton lattices, 930

density of difficult cases of, 1147

diffraction patterns of, 1082

enumeration of, 959

of fixed blocks, 582

history of, 943

in hyperbolic space, 1050

as invariant states of 2D CAs, 349

and Ising models, 1138

and melting points, 1194

NP completeness in, 984, 1145

Penrose, 932

see also Penrose tilings

and reversibility of 2D CAs, 1017

Truchet, 875

undecidability in, 1138, 1139

see also Domino problems

Time

alignment of in universe, 1021

branching in, 504

compression in PDEs, 732

computation between moments of, 1033

and definition of motion, 521

discreteness in, 1032

graphical representation of, 1031

in gravity and computation, 1130

in Hopi language, 1181

network for in multiway systems, 209

and randomness in causal networks, 494

in relation to space, 481-486

and single active cell, 487

in ultimate theory of physics, 486-508, 516-524

Time-and-motion studies

and causal networks, 1033

Time complexity (in computational complexity theory), 1142

Time dilation (relativistic), 524

Time Machine (science fiction book), 1031

Time reversal

in particle physics, 1019

and thermodynamics, 443, 1020

Time series analysis, 587, 1081, 1083

Time standards

as source of radio signals, 1188

Time travel, 1043

and character of time, 1031

and energy conditions, 1053

TimeConstraint

and avoiding undecidability, 1138

Timeline

of close approaches, 878

of my scientific activities, 864

of publications of mine, 881

of writing this book, 850

Times

combinator for, 1122

and NC computations, 1149

in ordering of math constructs, 1177

primitive recursive definition of, 907

Tippett, Leonard H. C. (England, 1902–1985)

and random number tables, 968

Tire treads

characteristic shapes of, 1183

Tit-for-tat strategy

in game theory, 1104

Titan

and extraterrestrial life, 1179