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 π, 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 π, 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–[2015])
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