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 mappings, 937, 963

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

Recurring decimals, 138, 912

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