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, 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 pi, e, 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, 997
     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