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

Tachyons, 1041
spin of, 1046

Taffy
as chaos theory example, 306
fracture in, 994

Tag systems, 9394
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, 840843
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 (A4)
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

Text editors, 88, 894

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, 441457
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, 620631
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, 182183
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, 211221
from 2 × 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, 481486
and single active cell, 487
in ultimate theory of physics, 486508, 516524

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