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 (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
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 × 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