Index



Reed-Muller codes, 1073

References
in this book, 850

Reflexes
vs. free will, 752

Reformation (religious)
and free will, 1135

Refractive indices, 1041

Regge, Tullio E. (Italy, 1931- )
and discrete spacetime, 1054
and spin networks, 1055

Regge calculus
and discrete space, 1027
variational principle for, 1052

Register machines, 97-102
for computing Sqrt, 1114
continuous versions of, 1128
emulated by arithmetic systems, 673, 1114
emulated by CAs, 661, 1112
emulating TMs, 671, 1114
encoded with Diophantine equations, 1161
halting of, 896, 1137
halting problem for, 1131
history of, 896
implementation of, 896
and intermediate degrees, 1131
and Life universality, 1117
with many registers, 1114
random initial conditions for, 949
small universal, 1121
and undecidability of tiling, 1139

Registers, shift
see Shift registers

Regular expressions, 957
matching of with repeats, 1143

Regular language complexity (finite automaton size), 958

Regular languages
analogs for networks, 1040
decidability of, 1137
and finite automata, 957
production rules for, 939
pumping lemma for, 944
and relations to CAs, 1138
rule 132 as recognizer for, 1109
see also Finite automata

Regularities
in biology, 384
compared to causes, 352
and computational reducibility, 746
inevitable and Ramsey theory, 1068
and lack of universality, 735
and meaning, 826, 1183
and perception, 549
and practical empirical math, 1090
in solar system, 313, 973
study of as purpose of science, 861

Regularity
axiom of in set theory, 1154

Reidemeister moves (for knots), 1046

Reif, Frederick (USA, 1927- )
and inspirational book cover, 864

Reissner-Nordström solution, 1133

Relations
in groups, 1141
in semigroups, 938

Relatively prime numbers
pattern of, 613

Relativism, 1131

Relativity
linguistic, 1181

Relativity theory, 516-524
and Bell's inequalities, 1065
and CPT invariance, 1019
history of, 1041
as introducing spacetime, 481
mechanism leading to, 522
and models of electron, 1044
and origin of uncertainty principle, 1058
posets in, 1041
and space vs. contents, 1028
standard treatment of, 1042
and time and computation, 1130

Reliability analysis, 977

Religion
and conflict with Darwinian evolution, 1001
and origins in animism, 1195
and Principle of Computational Equivalence, 845
see also Christianity, etc.
see also God
see also Theology

Renormalization, 1057
and discrete space, 1027
and electron self-energy, 1044
lack of in quantum gravity, 1054

Renormalization group, 955
and levels in ultimate theory, 471
and nesting, 989
and particle masses, 1046
and phase transitions, 983
and simple effective laws, 1026

Rényi, Alfréd (Hungary, 1921-1970)
and generalized entropies, 959

Rényi dimensions, 934

Repeatability
in computer experiments, 898
in intrinsic randomness generation, 323, 976, 976'
of turbulent flow, 382

Repeated squaring
applied to general rules, 1094
and computing powers, 615, 1093
for powers of 2, 749

RepeatedNull (...)
in regular expressions, 957

Repeats
and cryptanalysis, 599
finding maximal, 1071

Repetition periods
in block cellular automata, 1023
of digits in rationals, 912
of finite-size CAs, 260
for linear congruential generators, 974
longest in cellular automata, 1088
maximal in CAs, 951
for mobile automata, 887
and PSPACE completeness, 1142, 1147
of shift registers, 975
of stripes in rule 30, 871
in systems with symmetries, 950
see also Periodic points

Repetitive behavior
in animals, 1011
as basis for algorithms, 1141
in bird songs, 827
in cellular automata, 57, 954
in cellular automata in 2D, 954
in combinator evolution, 1123
and computational reducibility, 739
in continuous systems, 988
in digit sequences, 138
in DNA, 970
as exception to Second Law, 453
as familiar feature, 1106
in finite-size systems, 255, 267
formula for, 607
and history of math, 735
in human radio signals, 835
and lack of universality, 734
and local constraints, 213
and mechanical engineering, 829
in mobile automata, 72
in numbers, 988
origins of, 354-356
in ornamental art, 872
in PDEs, 988
and Poincaré recurrence, 1022
and Principle of Computational Equivalence, 722
recognizing visually, 582
in rule 30, 268, 700
in rule 250, 25
in sorting networks, 1142
structures with
see Localized structures
in three-body problem, 972
in Turing machines, 79
in whale songs, 1180

Repetitive initial conditions, 266, 954
and CA cryptography, 1087
perturbations in, 701

Repetitive sequences
block frequencies in, 1084
as initial conditions, 266
shortest programs for, 1186

ReplaceAll (/.)
basic examples of, 854
in implementing CAs, 867
and network evolution, 1038
and symbolic systems, 896

ReplaceList
and multiway systems, 937
and multiway tag systems, 1141
and traversing networks, 957

Replacements
for networks, 509
order of, 894
see also Order of updates
for strings
see Sequential substitution systems

ReplacePart
basic example of, 853
and initial conditions, 865

ReplaceRepeated (//.)
and symbolic systems, 898
and undecidability, 1138

Representation
and communication, 631
and definition of meaning, 827

Representation of numbers, 142
for data compression, 560
with Egyptian fractions, 915
as nested radicals, 915
as operator trees, 916
see also Bases (number)
see also Continued fractions
see also Digit sequences

Representations
of Boolean algebra, 1171
of operator systems, 805

Representing
see Emulation

Reproduction
see Self-reproduction

Reproduction curves
and iterated maps, 918

Reptiles
color vision in, 1075

Reptiles (nested tilings), 932

Resistors
1/f noise in, 969
and on-chip randomness, 970

Resolution
of printed pictures in book, 852

Resolution theorem proving, 1157

Resonant scattering
and 3-body problem, 973

Responsibility
and free will, 1135, 1136

Responsiveness
as definition of life, 823

Rest (rest of list)
basic example of, 853

Resultant
and CAD in real algebra, 1154

Retail store utilization
and Voronoi diagrams, 987

Retina (of eye)
pattern of cells in, 1007
structure of, 1075
and visual perception, 577

Retinoic acid
in embryo development, 1009

Return maps
and history of iterated maps, 918
and recognizing chaos, 972

Reversal
of digit sequences, 905

Reversal-addition systems, 125-127, 905

Reverse engineering, 1184

Reverse evolution
backtracking in CA, 1089

Reverse mathematics, 1167

Reverse Polish notation, 896

Reversibility, 435-441
of CAs at an angle, 1017
in causal networks, 495
of cellular automata
see Reversible cellular automata
of computation, 1018
in evolution of networks, 1040
in mappings, 960
in mobile automata, 1018
in multiway systems, 1018
and phase transitions, 983
and quantum computers, 1147
and quantum measurement, 542
in systems based on numbers, 1018
testing cellular automata for, 1017
and thermodynamic irreversibility, 442
undecidability of, 1138
see also Irreversibility

Reversible 3n+1 problem, 905

Reversible cellular automata, 436-441
block, 460
classification of, 1018
and dynamical systems theory, 961
emulated by ordinary CAs, 1018
history of, 1018
implementing, 1017
inverse rules for, 1017
and irreversible behavior, 452
from multiplication, 1093
number of, 1017
testing for, 1017, 1017'
testing for 2D, 1017
and texture generation, 1078
three-color, 436

Reversible logic, 1097
and quantum computers, 1147

Reviews of Modern Physics
my CA paper in, 880

Rewrite systems
and history of universality, 1110
for networks, 198, 508
sequential substitution systems as, 88, 894
see also Multiway systems
see also Sequential substitution systems

Reynolds, Osborne (Ireland/England, 1842-1912)
and Reynolds numbers, 996

Reynolds numbers, 376, 380, 996

Rhombic dodecahedron, 929, 987

Rhombo-hexagonal dodecahedron, 930

Rhymes
rules for in poetry, 875
in whale songs, 1180

Rhythm
rules for, 875

Ribbets
as sound of Cantor set, 586

Ribosomes, 1193

Ricci scalar curvature, 533
and constraints on tissue growth, 1010
and discretization of space, 1051
in expansion of metric, 1050
and volumes of spheres, 1050

Ricci tensor, 534
and Einstein equations, 1052
implementation of, 1049
for spacetime, 534

Rice, Henry G. (USA, 1920- )
and Rice's theorem, 1137

Richardson, Lewis F. (England/Scotland, 1881-1953)
and fluid turbulence, 997

Richat structure
circular shape of, 1187

Ricker, William E. (Canada, 1908-2001)
and iterated map for fish populations, 918

Riemann, G. F. Bernhard (Germany, 1826-1866)
and discrete space, 1027
and distribution of primes, 918
and nested curves, 934
and Riemann tensor, 1049

Riemann Hypothesis
and curve of zeta function, 148
and density of primes, 909
as Diophantine equation, 1161

Riemann mapping theorem
and growth shapes, 1010

Riemann tensor, 1049
difficulties with in networks, 1051
as form of curvature, 536
implementation of, 1049

Riemann zeta function, 148, 918
see also Zeta

Riemannian spaces, 1048

RiemannSiegelZ, 918
curve of, 148

Riemann-Siegel formula, 1134

Riesz, Frigyes (Hungary, 1880-1956)
and Riesz products, 1081

Riesz products, 1081

Rigid bodies
and analogy to quantum mechanics, 1059

Rigid rods
networks made from, 1031

Ring theory, 1153
axioms for, 773
and generalizing numbers, 1168
universality of, 784, 1159

Ringoids, 1171

Riots
instabilities in, 1014

Ripples
on ocean surfaces, 1001
as repetitive behavior, 988

Risch structure theorem, 1177

Rise time
of sounds, 1079

Risk
in financial systems, 1015

Risk functions
in parameter estimation, 1083

Rivers
and landscape structure, 1001
as showing nesting, 359, 988

RNA
and definition of life, 1178
and origin of life, 1179

RNGs
see Random number generators

Road traffic
1/f noise in, 969
flow instabilities in, 1014

Roads
straight visible from space, 1187

Robbins, Herbert E. (USA, 1915-2001)
and axioms for logic, 1151

Robbins axioms (for logic), 773, 1151, 1174
in terms of Nand, 808

Robinson, Abraham (England/Israel/USA, 1918-1974)
and non-standard analysis, 1172

Robinson, J. Alan (USA, 1930- )
and resolution theorem proving, 1157

Robinson, Julia B. (USA, 1919-1985)
and axioms for arithmetic, 1152
and Diophantine equations, 1161
and encodings of arithmetic, 1163
in Preface, xiii
and undecidability of field theory, 1160

Robinson, Raphael M. (USA, 1911-1995)
and axioms for arithmetic, 1152
and non-periodic tilings, 943
in Preface, xiii

Robinson arithmetic
axioms for, 773
incompleteness in, 800
universality in, 1152
unprovable statements in, 1169

Robotics
and history of complexity, 862
linkages in, 1129
and mobile turtles, 930

Robots
in fiction vs. humans, 629
free will for, 1135

Robust statistics, 1083

Robustness
in biology from randomness, 1002
from randomness, 1192
of software and complexity, 1069

Rock, Paper, Scissors game, 1105

Rock carvings
recognition of art in, 874

Rocks
as computationally equivalent to humans, 1196
crushing of, 988, 995
patterns of in landscapes, 1001
shaped by wind, 1183

Rogozhin, Yurii (Moldova, 1949- )
and Turing machines, 1119

Rolling of objects, as generating randomness, 305

Roman architecture
and nesting, 874

Roman art, 43, 873

Roman law
and free will, 1135

Roman military drill, 875

Roman number system, 1182

Roman numerals, 902

Roman religions
and animism, 1195

Romberg integration, 1134

Rome (Italy)
mosaics in, 872

Root (polynomial root)
and continued fractions, 914
and entropies of CAs, 958
and fractal dimensions for additive rules, 956
and generalized special functions, 1092
and hard hexagon model, 959
and linkages, 1129
and origin of group theory, 1153

Root finding
attractor basins in, 1101
and iterated maps, 918
see also Newton's method

Root vectors
and sphere packings, 987

Roots
linguistic, 1100

Rope
nesting in, 874, 1183

Rose window
of Lincoln cathedral, 873

Rosen, Nathan (USA/Israel, 1909-1995)
and EPR experiment, 1058

Rosenblatt, Frank (USA, 1928-1971)
and perceptrons, 1099

Rosenblueth, Arturo (Mexico, 1900-1970)
and reaction-diffusion, 1013

Rosetta stone, 1185

Rosette patterns, 873
in four-color printing, 1078

RoShamBo game, 1105

RotateLeft
basic example of, 853
in CA evolution, 865

Rotating vacuum solution to Einstein equations, 1053

Rotation
absolute definition of, 1047
particle production in, 1062

Rotation group
and spin, 1046
and spin networks, 1055

Rotational symmetry
in cellular automaton rules, 928
see also Isotropy
see also Symmetry

Roth, Klaus F. (England, 1925- )
and rational approximations, 915

Rotor machines
for cryptography, 1085

Roughness
in aggregation systems, 978
of crystal surfaces, 993
effect on splashes of, 1000
effects of microscopic, 996
in fracture surfaces, 994
in random walk boundaries, 977
and randomness from initial conditions, 305
of surfaces, 1077
of surfaces and repeatable randomness, 976

Roulette
randomness in, 306, 968, 969

Roundoff errors
and chaos experiments, 919
and continuous CAs, 921
in molecular dynamics, 864
see also Numerical analysis

Routing in networks, 1192