# 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 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

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