# Index

Rabbit (Fibonacci) sequences, 891

Racah coefficients

see 6j symbols

Radar

random pulses for, 970, 1192

as source of radio signals, 1188

Radiation

of structures from rule 37R, 456

and thermodynamics, 1021

in vacuum field theory, 1062

Radicals

continued fractions for, 144

digit sequences for, 139

and linkages, 1129

nested, 915

and periodic points of iterated maps, 955

solving equations in, 945

see also Quadratic irrationals

see also Root

see also Sqrt

Radio astronomy

noise in, 1187

and SETI, 835, 1180, 1188

Radio noise, 302

and SETI, 836

Radio signals

extraterrestrial, 835, 1180

of human origin, 1188

of natural origin, 1187

and shift registers, 1086

Radioactive decay

and quantum field theory, 1057

randomness in, 970

relativity theory applied to, 1043

Radiolarians

and circle packings, 985

forms of, 385, 1011

skeletons as animal artifacts, 1184

Radix of numbers

see Bases (number)

Radó, Tibor (Hungary/USA, 1895–1965)

and Busy Beaver Problem, 889

Railroads

as speculative stocks, 1015

as visible from space, 1187

RAM (random-access memory)

emulated by CA, 663, 1112

Ramanujan, Srinivasa A. (India/England, 1887–1920)

and almost integers, 915

and divisor sequences, 910, 911

and experimental math, 899

Ramsey theory, 1068

unprovability related to, 1163

RAND Corporation

and random number table, 968

Random

as intrinsic randomness generator, 317

Random-access memory (RAM)

emulated by CA, 663, 1112

Random-dot stereograms, 1076

Random groups, 938

Random initial conditions, 223-296

for CA doing computations, 1109

as origin of randomness, 304-314

in reversible CAs, 438

in systems other than CAs, 949

Random matrices, 977

Random models

see Probabilistic models

Random networks, 480, 963, 1038

Random number generators, 317, 974

and history of complexity, 49

and iterated maps, 919

as precursors to my work, 879

see also Randomness generators

Random packings, 986

Random phase approximation

in path integrals, 1061

Random programs

and complexity in biology, 388

crashing of, 1183

on practical computers, 101

typical behavior of, 23

Random proteins, 1184

Random rules

typical behavior of, 23, 723

Random sequences

spectra of, 587

weighted, 976

Random trees, 1084

Random walks

and 3n+1 problem, 904

and continuous behavior, 327

and diffusion-limited aggregation, 979, 994

from digits of pi, 136, 912

and dimensions of networks, 1030

with exponential waiting, 969

and fracture patterns, 995

isotropy of, 980

in iterative improvements, 985

in mobile automata, 75

and nesting, 990

and path integrals, 1057

of prices in markets, 1014

and randomness tests, 1085

in rule 30 pattern, 871

self-avoiding, 978

spectrum of, 1082

Randomization

on inspirational book cover, 17, 864

in mechanical systems, 968

in semiconductor devices, 970

Randomized algorithms, 1085, 1142

Randomness

algorithmic, 1067

applications of, 1192

in astronomy, 313

in biological pigmentation patterns, 1013

in biology, 970

in boiling, 994

cells in animals generating, 1011

in class 3 systems, 261

in combinator evolution, 713

compared to complexity, 557

in computer systems, 970

continual injection of, 947

in crumpling of paper, 996

in cyclic tag systems, 96

and data compression, 572

definition of, 316, 552-556

deterministic behavior from, 979

dictionary definition of, 1068

in digit of square roots, 139

in digits of pi, 138

in digits of powers, 119

in distribution of primes, 134

in early universe, 1021

from the environment, 301-304

evolution from, 223-296

as explained by chaos theory, 971

of facts in math, 820

in financial markets, 429, 1014

in fluid flow, 376

in forms of crystals, 373

in fracture, 374

and free will, 752

generated by *Mathematica*, 973

in heartbeats, 1002

history of defining, 1067

human generation of, 1104

increasing popularity of, 1192

from initial conditions, 304-314

intrinsic generation of, 315-326

and irreversibility in physics, 442

mechanical sources of, 968

mechanisms for, 299-326

in mobile automata, 74

in multiway systems, 205

in network systems, 202, 936

and NP completeness in rule 30, 770

in ocean surfaces, 1001

in operation of brain, 1135

in optical system, 310

and origin of continuity, 327

paper of mine on, 882

and percolation theory, 983

in physiological processes, 1011

in primitive recursive functions, 908

in protein sequences, 1184

in quantum chaos, 1056

and quantum measurement, 1063

in quantum systems, 539, 970, 1064

randomized algorithms as tests for, 1085

in recursive sequences, 130

in register machines, 100

repeatable intrinsic, 323

in rolling dice, 305

in rule 30, 27

in sequential substitution systems, 92

in solar system, 973

in statistics, 593

in substitution systems, 88

in tag systems, 94

tests of, 1067, 1084

in three-body problem, 314

in TM running times, 762

in tossing coins, 305

in turbulent fluid flow, 379

in Turing machines, 79

in Turing machines in 2D, 184

ultimate definition of, 1068

in universe that branches, 506

and visual perception, 583

Randomness generators

cellular automaton, 975

cryptographic, 975

failures of, 969

generalized Fibonacci, 975

linear congruential, 974

quadratic congruential, 975

shift register, 974

see also Random number generators

RANDU (random number generator), 974

Range

basic example of, 853

Rankine, William J. M. (Scotland, 1820–1872)

and vortices in ether, 1044

Raspberries

phyllotaxis in, 409

Raster

in CA graphics, 865

Raster displays

lines on digital, 916

RasterGraphics

and CA graphics, 868

Rate equations, 984

Rational agents

and game theory, 1104

and notion of purpose, 1185

Rational choice theory

and responsibility, 1136

Rational design

in chemistry, 1194

Rational expectations

difficulty of testing for, 1015

in economics, 429

Rational functions

of complex variables, 933

as generating functions, 1091

integrals of, 916

and periodic points, 959

and regular languages, 958

Rational maps, 918

and Apollonian packings, 986

Rational numbers

approximation by, 915

digit sequences of, 138, 912, 1084

number of, 1127

pattern based on, 950

and periodic iterated maps, 955

and randomness from initial conditions, 307

and spectra, 1081

Rationalism

and math in science, 860

Rationality

bounded of players, 1104

Raup, David M. (USA, 1933– )

and shapes of shells, 1008

Ray, John (England, 1627–1705)

and natural theology, 861

Rayleigh number, 1000

Rayleigh speed, 995

Rayleigh-Taylor instabilities

and repetitive behavior, 988

Rays (fish)

patterns in teeth of, 1007

r.e. (recursively enumerable) sets, 1138

r.e. degrees (arithmetic hierarchy), 1139

Reachable states, 275, 957

see also Attractors

Reaction-diffusion processes, 1012

and animal growth, 419

and animal pigmentation, 427, 1004, 1013

and cellular automata, 427

and complexity research, 862

and history of CAs, 878

modes in, 1013

and pattern formation, 947

and plant growth, 409

and shell patterns, 1012

Reaction rate equations, 984

Reactions (chemical)

repeatable randomness in, 976

and undecidability, 1194

Reading distance

and texture recognition, 1076

Real algebra

axioms for, 773, 1153

as not universal, 1160

Real analysis

axioms for, 1155

Real numbers

and computability, 1128

constructible, 1129

countable models of, 1172

number of, 1127

and randomness from initial conditions, 308

Turing computable, 1128

RealDigits (digits of real number)

implementation of, 901

and weighted random sequences, 976

Reasoning

automated

see Automated theorem proving

automated mathematical, 1157

predicate logic as model for, 1152

see also Intelligence

see also Thinking

Rebooting

random seed after, 970

Receptors

in auditory system, 1079

in color vision, 1075

other types of, 1105

in visual system, 577, 1075

Reciprocals

digit sequences of, 730

and Egyptian fractions, 915

Recognition

of artifacts, 828, 1183

of CA patterns, 621

of extraterrestrial intelligence, 825

of formal languages, 939

of objects, 1076

of randomness, 317

see also Perception

Recombination

and randomness in biology, 970

Record (phonograph)

for extraterrestrials, 1190

Recreational computing

Game of Life in, 949

and history of CAs, 877

and history of complexity, 50

and universality of Life, 693

Recreational logic

and combinators, 898

Recreational mathematics

complexity in, 49

and number theory, 910

randomness in, 1192

Rectangular numbers, 909

Recurrence relations, 128-131

for Fibonacci numbers, 891

and iterated maps, 906

linear, 906

numbers from, 916

and square roots, 913

and time series, 1083

Recurrent

see Repetitive

Recursion

in backtracking algorithm, 1089

as basis for algorithms, 1141

compared to nesting, 990

and history of CAs, 877

induction as basis for, 1152

in substitution system rules, 1033

see also Fractals

see also Nesting

Recursion relations, 128

Recursive axiomatizability, 1176

Recursive functions

and Church's Thesis, 1125

emulating tag systems, 1121

emulating Turing machines, 1121

general, 907

as idealization of math, 1150

not primitive recursive, 908

primitive, 907

and proof of Gödel's Theorem, 1158

and recursive sets, 1138

undecidability in, 1136

universality of, 1121

Recursive sequences, 128-131

history of, 907

inverse of, 906

sounds from, 1080

see also Nested sequences

see also Substitution systems

Recursive sets, 1138

Recursive subdivision

and data compression, 568

implementation of, 1072

and lossy compression, 572

and substitution systems, 187

Recursively enumerable (r.e.) sets, 1138

Red shift

and brightness of night sky, 1021

Reduced arithmetic

see Robinson arithmetic

Reducibility

see Computational reducibility

Reductio ad absurdum

as scheme for proofs, 1177

Reduction

see Emulation

Reduction of colors

in cellular automata, 655

in Turing machines, 669, 1113

Reduction of wave packets, 1063

Reduction ordering

in completion algorithms, 1037

Reductionism

as theme of existing science, 3

Redundancy

and cryptanalysis, 600, 1086

in data, 1069, 1181

in error-correcting codes, 1101

in extraterrestrial signals, 836

in languages, 1181

and role of analysis, 549

Redundancy laws (in logic), 817