Index
U(1) (group)
and additive systems, 953
U-numbers (Ulam sequences), 908
Ukraine
art from, 873
Ulam, Stanislaw M. (Poland/USA, 1909–1984)
and CAs, 876, 877, 879
and generalized CAs, 928
and iterated maps, 918
in Preface, xiii
and Ulam sequences, 908
Ulam sequences, 908
Ulam's problem (3n+1 problem), 904
Ultimate theory of physics, 465–545
and amount of information, 1133
elementary particles in, 525–530
and extraterrestrial trade, 1191
general features of, 465–471
gravity in, 530–537
history of, 1024
mass in, 528
numerology and, 1025
quantum phenomena in, 537–545
searching for, 466
space in, 472–486, 516–524
and theology, 1025
time in, 486–508, 516–524
undecidability of consequences of, 1027
uniqueness of, 470
and universe as computer, 1026
verifiability of, 469
Ultrafilters
and non-standard arithmetic, 1169
Ultraspherical functions
and rule 150 pattern, 612
Unary operations
and generalized additivity, 952
Unary representation of numbers, 560, 1070
and CA fluids, 1000
historical use of, 1182
in lambda calculus, 1121
and NP completeness, 1145
Unbiased estimators
for entropy, 959, 1084
Unbounded growth
in class 4 systems, 289
in Game of Life, 965
in rule 110, 293
Uncertainty principle, 1058
as basic quantum effect, 1059
character of as principle, 1126
and vacuum fluctuations, 1062
and virtual particles, 1046
Unconscious thinking, 1136
Undecidability, 753–757
in algebra, 1138
of algorithmic randomness, 1067
of applicability of Baker's method, 1164
of axiom system correctness, 1170
in biology, 1138
in cellular automata, 1138
in chemical synthesis, 1194
in classification of CAs, 948
in combinatorics, 1138
compared to math impossibility, 1137
of completion algorithms, 1037
in computer science, 1138
of confinement in QCD, 1062
of consequences of ultimate theory, 1027
of context-free language equivalence, 1103
degrees of, 1139
density of, 1137
Diophantine equation with, 786
of entropy values, 958
of equivalence in operator systems, 802
of equivalence of manifolds, 1051
of forcing of operators, 1172
in game theory, 1105
of halting problem, 1128
history of, 1136
vs. independence, 1159
in lambda calculus, 1136
in Mathematica, 1138
in mathematical logic, 1138
mentioned in psychology, 1136
in multiway systems, 779, 1136
in nature, 1138
as not relevant to nature, 1132
vs. NP completeness, 769
in number theory, 1138
in operator systems, 815
of phase transitions, 1138
in physics, 1138
of P=NP problem, 1146
and proofs, 779
in quadratic Diophantine equations, 1164
and quantum measurement, 1064
in recursive functions, 1136
and sets, 1138
of structure equivalence in networks, 1045
of surjectivity for 2D CAs, 960
in symbolic integration, 1177
in tag systems, 1136
and three-body problem, 1138
in tiling problems, 942, 1139
of undecidability, 1138
of universality, 1127
without universality, 734
in word problems, 1141
Undefined function values
in Turing machines, 1143
Unfailing completion algorithms, 1037
and automated proofs, 1158
Unified field theory (of Einstein), 1025, 1028
Unified models (in particle physics), 1043
Uniform distribution
and iterated maps, 919
and linear congruential generators, 320
mod 1, 903
of multiplicative sequences, 903
and plant phyllotaxis, 1007
of powers, 903
of sequences, 904
of unbounded quantities, 1070
Uniform sampling
as application of randomness, 1192
Uniform spectra, 1081
origins of, 988
Uniform tag systems, 893
see also Substitution systems
Uniformity
in hashing, 622
origins of, 353
in rule 254 cellular automaton, 24
visual approximations to, 1078
Union
basic example of, 853
and encoding integers as sets, 1160
and finite set theory, 1171
in multiway systems, 937
theorems about, 1168
Uniqueness
of humans, 1195
in Navier–Stokes , 996
of patterns from CAs, 956
of solutions to equations, 940
of solutions to PDEs, 923
of ultimate theory of physics, 470
Unitarity (in quantum mechanics), 1059
Unitary matrices
and quantum computers, 1147
Univalve shells, 1008
Universal algebra, 1171
of Whitehead, 1150
Universal cellular automata, 644–656, 1110
history of, 1115
and rule 110, 675–691
Universal circuits, 1148
Universal computation
see Universality
Universal constructor, 1193
Universal Diophantine equations, 786, 789, 1160
history of, 1161
and polynomial values, 1162
Universal languages
for extraterrestrial communication, 1189
and human thinking, 1099
and Leibniz, 1109, 1149
and logical positivism, 1181
and theories of communication, 1181
Universal primitives
for logic, 1173
for multivalued logic, 1175
for quantum computers, 1148
for reversible logic, 1098
Universal register machines, 1121
Universal spaces
see Cellular automata
Universal system
in nanotechnology, 1193
Universal Turing machines
and cellular automata, 1115
Minsky's, 1119
and running times, 764
simple, 706
Universality (apparent)
history of, 967
of mathematics, 860
in models, 992
of natural systems, 298, 718
in nature and elsewhere, 4
Universality (computational), 5, 642–644
and algorithmic information, 1067
of arithmetic systems, 673
automated proving of, 1127
in axiom systems, 784
of cellular automata, 644
of cellular automata in 2D, 693
and class 4 behavior, 691
in classes of systems, 1123
in combinators, 711
and complexity, 643
and computational irreducibility, 742
in computer languages, 642
criteria for, 1126
in cyclic tag systems, 669
density of, 1126
difficulty of proving, 698, 722
in Diophantine equations, 1164
and financial markets, 1015
of general recursive functions, 907
of group theory, 1159
history of, 1109
implications of, 674
and intermediate degrees, 734
lack of with nesting, 734
lack of with repetition, 734
and language translation, 643
in Mathematica, 1110
of mobile automata, 664
and natural science, 643
as not relevant to nature, 1132
vs. NP completeness, 766
in operator systems, 815
and oracles, 1126
and P completeness, 1149
of Peano axioms, 1152
of predicate logic, 1159
and Principle of Computational Equivalence, 717
proofs of, 722
of pure predicate logic, 1152
of recursive functions, 1121
of register machines, 672
removed by adding axioms, 1159
and reversibility, 1019
of rule 30, 734
of sequential substitution systems, 667
of substitution systems, 666
of symbolic systems, 668
in tag systems, 667, 1120
in three-body problem, 972
threshold of, 675
threshold of in CAs, 694
in totalistic cellular automata, 693
in Turing machines, 665, 706–711
ubiquity of, 690, 718
and undecidability, 1137
undecidability of, 1127
Universality (critical phenomena)
in iterated maps, 921
and phase transitions, 983
Universality theorem
for zeta function, 918
Universals
in computer languages, 1182
and decoding dead languages, 1185
in human languages, 1103, 1181
Universe
as an artifact, 1191
basic cosmology of, 1055
and Church's Thesis, 1126
initial conditions for, 1026
mind as microcosm of, 1196
vacuum solutions for, 1053
wave function for, 1063
see also Cosmology
Universe, theory of
see Ultimate theory of physics
Unix operating system
and my early work, 864
random seeds in, 970
and regular expressions, 958
Unpredictability
and free will, 752
history of, 1132
in randomness from environment, 301
see also Predictability
Unprovability
see Undecidability
Unprovable statements
about symbolic systems, 897
in math, 1163
Unreliable components
and phase transitions, 981
Unrestricted grammars, 939
Unsolvability
Diophantine equation showing, 786
in math, 1137
of quintic equations, 1132
of three-body problem, 972
see also Undecidability
Unsolved problems
in number theory, 789, 1162, 1166
paper of mine on, 882
in science of this book, 856
Unsupervised learning, 1102
Unwinding
of primitive recursion, 907
Upside-down visual images, 626
Ur-theory, 1027
Urban planning
see Cities
Urey, Harold C. (USA, 1893–1981)
and origin of life, 1179
URMs (universal register machines), 1121
Uruk, Mesopotamia, 873
U.S. government
and artificial intelligence, 1099
and cryptography, 975, 1085
User interfaces
and concept of halting, 1137
graphical vs. language, 631
history of, 1102
Utah
and features seen from space, 1187