# Index

Fabric

wrinkling of, 996

Face-centered cubic (fcc)

lattice, 930

sphere packing, 986

Voronoi diagram, 987

Faces (geometrical)

in deformable packings, 988

and discrete spaces, 1051

in planar networks, 1038

Faces (human)

development of bones in, 1010

parametrization of, 1010

random variations in, 1192

recognition of, 626

Faceted crystal growth, 370

Factor (polynomial factorization)

analog for Boolean formulas, 1095

and cycles in shift rules, 963

and quadratic congruential generators, 975

randomized algorithm for, 1192

and shift register periods, 975

Factorial (n!)

encoded as integer equation, 1160

and examples of universality, 1110

and hypersphere volume, 1050

leading digits in, 914

and number of reversible block cellular automata, 1023

number with digits at, 914

and QED perturbation series, 1060

as recursive sequence, 906

and transcendental numbers, 914

see also Gamma

Factorial2 (double factorial)

and isotropic tensors, 980

Factories

and self-reproducing systems, 876

FactorInteger (integer factorization)

and arithmetic system encoding, 1115

basic methods for, 1090

difficulty of evaluating, 1134

and Fermat's Last Theorem, 1166

and multiplicative digit sequences, 902

and MultiplicativeOrder, 1147

and NP completeness, 1146

and number of commutative groups, 1172

and quantum computers, 1148

running times for, 1090

unique domains for, 915

Factorization

of cellular automata, 956

False

definition from And and Not, 817

Falsifiability of models, 365

Faltings theorem (Mordell conjecture), 1164

Family trees

and substitution systems, 893

Fano, Robert M. (USA, 1917– )

and data compression, 1069

Farey sequences, 916

Farm animals

growth of, 1010

Fast algorithms, 1141

Fast Fourier transform (FFT)

recursive algorithm for, 1142

see also Fourier

Fast Walsh transform, 1073

Fastest programs, 760

Fate

vs. randomness, 967, 1135

Fax

data compression in, 1070

fcc (face-centered cubic)

lattice, 930

sphere packing, 986

Voronoi diagram, 987

Feasible computations, 1143

see also Polynomial time

Feathers

coloration of, 1012

Feature detection

as basis for perception, 549

in human visual system, 577

Fedorov, Evgraf S. (Russia, 1853–1919)

and shapes of 3D domains, 929

Feedback

control and cybernetics, 862

in growth of bones, 1010

in visual system, 1075

Feedback shift registers, 974

see also Shift registers

Feigenbaum, Mitchell J. (USA, 1944– )

and computer experiments, 899

and iterated maps, 921

in Preface, xiii

Feigenbaum's constant, 913

Fejes Tóth, László (Hungary, 1915– )

and circle packing, 985

Fermat, Pierre de (France, 1601–1665)

and Fermat's Last Theorem, 1166

and primes, 909

Fermat primes conjecture

as unsolved problem, 1166

Fermat's Last Theorem, 1166

and Diophantine equations, 1164

as having long proof, 779

and number theory history, 910

and sparse solutions, 945

Fermat's little theorem, 909

Fermat's principle (in optics), 1061

Fermi, Enrico (Italy/USA, 1901–1954)

and computer experiments, 879, 899

and extraterrestrial contact, 1191

and statistical mechanics, 1020

Fermi-Pasta-Ulam experiment, 1020

Fermilab

circular shape of, 1187

Fermions

and basic quantum effects, 1059

and classical limits, 1059

spin-statistics of, 1046

Ferns

branching in, 401, 1004

and iterated function systems, 1005

Ferrite core memory, 864

Ferrites

as components in technology, 1195

Ferrofluids

maze-like patterns in, 1013

phyllotaxis-like patterns in, 1007

Ferromagnetic materials

Ising model for, 981

phase transitions in, 981

Fertilization

randomness in, 970

Feynman, Carl R. (USA, 1962– )

and cryptanalysis of rule 30, 1087

in Preface, xiii

Feynman, Richard P. (USA, 1918–1988)

and cryptanalysis of rule 30, 1087

and discrete quantum models, 1060

and discreteness of space, 1027

and path integrals, 1057

and physics and computation, 1126

in Preface, xii, xiii, xiv

Feynman diagrams, 1060

exact calculations of, 1133

history of, 1057

Monte Carlo methods in, 1192

not as mechanistic model, 1026

in QCD, 1061

for quantum gravity, 1054

and random networks, 1039

vs. space networks, 1040

and spin networks, 1055

FFT (fast Fourier transform)

digit reversal sequences in, 905

implementation of, 1074

multiplication using, 1093

recursive algorithm for, 1142

see also Fourier

Fiber bundles

and continuum limits of networks, 1030

and gauge theories, 1045

Fiber optics

vs. broadcasting, 1188

Fibers (biological)

and folding of tissue, 417

Fibonacci, Leonardo (Pisano) (Italy, ~1170 – ~1250)

and digital numbers, 902

and Fibonacci numbers, 891

and rabbit populations, 1002

and tables of primes, 910

and trees, 893

Fibonacci (Fibonacci sequence)

difficulty of making with CAs, 1186

and entropy in rule 32, 958

generalized, 891

generalized for randomness generation, 975

generating function for, 1091

as initial condition for rule 60, 1091

leading digits in, 914

and multiway system states, 205

and multiway systems based on numbers, 939

number with digits at, 914, 1070

in ordering of math constructs, 1177

and plant phyllotaxis, 1006

and polyominoes, 943

as precursors to my work, 878

properties of, 890

and prosody, 875

and randomness generators, 975

and recursion history, 907

as recursive sequence, 128

and rule 150 pattern, 885

as solution to Diophantine equation, 1161

and spectral maxima, 1081

and substitution systems, 82, 890

as term in continued fraction, 913

uniform distribution mod 1, 904

as values of polynomial, 1161

Fibonacci multiway system, 205

Fibonacci number representation, 560, 1070

and multicolor encodings, 1111

as non-power base, 902

and substitution systems, 892

Fibonacci substitution system, 83

and cyclic tag system, 895

and cyclic tag systems, 96

in music, 875

and Penrose tilings, 932

properties of, 890

and sine curves, 147

spectrum of, 586, 1081

two-dimensional, 932

Field Museum of Natural History, 1011

Field operators

measurement of, 1065

Field theory (in abstract algebra), 1153

axioms for, 773

decidability with ordering predicates, 1159

and generalizing numbers, 1168

universality of, 1159

see also Finite fields

Field theory (physics)

history of, 1024

nonlinear PDE as, 923

quantum, 1061

see also Quantum field theory

Fields (agricultural)

patterns of from space, 1187

Fifths (musical chords)

curves of, 146

perfect, 1079

Fig leaves, 1005

Figurate numbers, 911

Filters (for data)

cellular automata as, 225

in visual perception, 1076

Filters in posets, 1040

Final cause, 1185

Final theory

see Ultimate theory of physics

Financial systems

applications to, 429-432

data from as source of randomness, 969

history of models of, 1015

meaning of random data in, 1183

simulations of, 968

using randomness to verify contracts in, 968

FindMinimum

and network layouts, 1031

FindRoot

difficulty of evaluating, 1134

iterative algorithm for, 1141

Fine structure constant (alpha)

numerology for, 1025

and perturbation theory, 1057

Fine tuning

and self-organized criticality, 989

Fingerprints

origin of patterns in, 1013

randomness in, 1014

Fingers

formation of human, 419

Finite automata

and attractors for CAs, 277

and Boolean functions, 1097

and CA encodings, 1119

and defining complexity, 1069

and formulas for nesting, 608

and groups, 1141

history of, 958

lower bounds in, 1143

minimization of, 957

as networks, 957

probabilistic, 1084

and regular languages, 939

and semigroups, 1153

and soundex system, 1100

spectra of, 1081

and substitution systems, 891, 931, 1091

total number of, 957

Finite axiomatizability, 1176

Finite complement languages, 941

2D generalizations, 959

and excluded blocks, 958

and repetition in 1D CAs, 954

Finite differences

and CA diffusion, 1024

and continuous CAs, 921

explicit schemes and sequential cellular automata, 1035

and history of CAs, 876

isotropy in, 980

methods based on, 940

neighborhood compared to cellular automata, 928

for PDEs, 924

and reaction-diffusion, 1013

Finite element methods, 940

Finite fields

as not universal, 1160

see also Additive cellular automata

see also Field theory (in abstract algebra)

Finite groups

axioms for, 1176

Cayley graphs of, 1032

as extraterrestrial messages, 1190

rules for, 938

Finite impulse response

and sequential CAs, 1035

Finite-size scaling

in Ising models, 983

Finite-size systems, 255-260, 961

Finite state machines

see Finite automata

Finitely presented groups

see Groups

Finitistic mathematics, 1158

Finkelstein, David R. (USA, 1929– )

and discreteness of space, 1027

in Preface, xiii

Finnish

logic operations in, 1173

Fins (heat exchanger)

characteristic shapes of, 1183

Fire

as artifact, 1183

as basis for universe, 1125

as visible from space, 1187

Firing of neurons

in neural networks, 1102

repeatable randomness in, 976

Firing squad problem (in cellular automata), 876, 1035

First digits, 914

of powers, 903

First Law of Thermodynamics, 1019

First-order phase transitions, 981

Fisher, Ronald A. (England, 1890–1962)

and random number tables, 968

Fisher-Tippett distribution, 977

Fishes

color vision in, 1075

iterated maps for populations of, 918

pigmentation patterns of, 389, 426

shapes of related by transformations, 1010

Fishhooks

characteristic shapes of, 1183

Fit (least-squares fit), 1083

Fitness

optimization of in biology, 386

and purpose, 1185

Fitting of clothes

and allometry, 1010

FitzGerald, George F. (Ireland, 1851–1901)

and relativity theory, 1041

FitzGerald-Lorentz contraction, 1041

Five-body problem, 1130

Five-fold symmetry

in biology, 1007

cellular automata with, 930

and Penrose tilings, 932, 943

in quasicrystals, 994

Five-neighbor rules (in CAs), 927

Fixed points

in 1D cellular automata, 224, 954

in 2D cellular automata, 954

as attractors, 276

of blocking transformations, 270, 955

in combinator evolution, 712, 1122

for differential equations, 961

in Game of Life, 964

in iterated maps, 955, 961

in *Mathematica*, 1137

of pigmentation patterns, 427

in recursive evaluation, 906

of sandpile model, 989

and satisfying constraints, 348

in symbolic systems, 897

undecidability of, 1138

FixedPoint

and gradient descent, 985

undecidability in, 1138

FixedPointList

and length prefixed numbers, 1070

and prime implicants, 1095

Flagellated microorganisms

random motion of, 970

Flames

as self-organizing systems, 824

as self-reproducing, 1178

Flash photography

and forms of splashes, 1000

Flat (associative)

and associative CAs, 886, 956

and Boolean functions, 1173

and confluence property, 1037

and fast evolution rules, 1094

and generalized additivity, 952

and sequential substitution systems, 894

Flat spectra, 1081

Flatness (geometry)

of growing sheets of tissue, 1007

Flatten

basic examples of, 853

and correspondence systems, 1139

generalized to 2D, 931, 1073

generalized to any dimension, 932

and sequence equations, 944, 1141

Flatworm

pigmentation pattern on, 426

Flicker noise, 969

see also 1/f noise

Flint arrowheads, 1183