Index



U(1) (group)
and additive systems, 953

U-numbers (Ulam sequences), 908

UFOs, 1180, 1183

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, 465545
and amount of information, 1133
elementary particles in, 525530
and extraterrestrial trade, 1191
general features of, 465471
gravity in, 530537
history of, 1024
mass in, 528
numerology and, 1025
quantum phenomena in, 537545
searching for, 466
space in, 472486, 516524
and theology, 1025
time in, 486508, 516524
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, 753757
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, 644656, 1110
history of, 1115
and rule 110, 675691

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 objects, 724, 1127

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, 642644
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, 706711
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