# 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