# Index

Glaisher, James W. L. (England, 1848–1928)

and binomials mod k, 870

Glare filters (polarizers), 1064

Glass (material)

as amorphous material, 994

fracture in, 994

Gleick, James W. (USA, 1954– )

and chaos theory, 972

Glider gun

in code 1329, 288

in Game of Life, 965

in rule 110, 293, 964

Gliders, 284

in continuous CAs, 160

and emulation of Nand, 1117

in Game of Life, 249, 964

in rule 110, 292, 964

see also Localized structures

Global minima, 347

Global Positioning System

see GPS

Globular clusters

and thermodynamics, 1021

Glueballs (in QCD), 1061

Gluons (in QCD), 1057

confinement of, 1061

Glycerine

viscosity of, 996

Gnomons

and Euclid's algorithm, 915

and forms of growth, 1008

and substitution systems, 932

Go, game of, 875

Goats

fortune-telling from, 968

God

and character of space, 1028

and complexity, 861

and free will, 1135

identified with universe, 1196

and objects in nature, 828

and origin of complexity, 3

and phenomena in astronomy, 834

and physics as intelligence, 1191

and purpose for universe, 1185

as source of complexity in biology, 1001

and ultimate theory of physics, 1025

and universe as intelligent, 1196

see also Religion

see also Theology

Gödel, Kurt F. (Austria/USA, 1906–1978)

and character of math, 1176

and consistency of arithmetic, 1168

and defining computability, 1126

and experiment in math, 899

and Gödel's Theorem, 879, 1158

and origins of universality, 1110

and predicate logic, 1152

and register machines, 896

and undecidability, 1136

Gödel beta function, 1121

and primitive recursion, 908

Gödel numbers

and encoding lists, 1120

and history of universality, 1110

Gödel's Completeness Theorem, 1152, 1167

for equational logic, 1172

Gödel's Theorem, 1158

and arithmetic systems, 673

and Church's Thesis, 1125

and determinism, 1132

and Diophantine equations, 1161

encoding of statements in, 785

encodings used in, 816

and free will, 1135

and history of math, 1149

and history of universality, 1110

as limitation on math, 7, 1135

practical relevance of, 791

as precursor to my work, 879

proof of using rule 110, 786

and truth, 1167

and universality of arithmetic, 784, 1152

and unprovable statements, 782

use of recursive functions in, 907

Gods

animism and, 1195

as source of randomness, 967

Goethe, Johann W. v. (Germany, 1749–1832)

and morphology, 1004

Golay, Marcel J. E. (USA, 1902–1989)

and error-correcting codes, 1101

and hexagonal CAs, 928

Golay codes

and sphere packings, 987

Golay neighborhood (hexagonal cellular automata), 928

Gold

hopper crystals in, 993

Goldbach, Christian (Russia, 1690–1764)

and polynomials for primes, 909

Goldbach's Conjecture, 135, 911

stated in Peano arithmetic, 1162

true if unprovable, 1167

as unsolved problem, 1166

GoldenRatio

and 2D substitution systems, 932

and entropy in rule 32, 958

and Fibonacci encoding, 1070

and general study of form, 967

and growth rate of multiway system, 205

and Penrose tilings, 932

as Pisot number, 903

and plant phyllotaxis, 408, 1006

properties of, 890

and running time of Euclid's algorithm, 1147

and spectra, 1081

Golf balls

and circle packings, 985

Golomb, Solomon W. (USA, 1932– )

and nonlinear shift registers, 878

and polyominoes, 943

in Preface, xiii

and shift registers, 879, 1088

Goodstein, Reuben L. (England, 1912–1985)

and Goodstein sequences, 1163

Goodstein sequences

proofs about in set theory, 1160

and unprovability, 1163

Goosefoot leaves, 1006

Gosper, R. William (USA, 1943– )

and dragon curves, 893

and experimental math, 899

and Game of Life, 965

in Preface, xiii

Gothic windows

nesting in, 873, 874

Government control

and computational irreducibility, 1132

Government regulation

of games of chance, 1084

GPS (Global Positioning System)

and SETI, 1190

and shift registers, 1086

and time dilation, 524, 1042

Gradient descent

implementation of, 985

in neural networks, 1102

for satisfying constraints, 344

Gradualism

in biological evolution, 395

Grain patterns

and repeatable randomness, 976

Grains (in solids)

evolution of, 1039

and Voronoi diagrams, 987

Grammar-checking software, 1104

Grammars

and concept of programs, 860

context-free, 939, 1103

context-sensitive, 939

of formal languages, 938

of human languages, 630, 1103, 1181

of math expressions, 1150

of ornament, 872

random, 1084

and redundancy, 1086

regular, 939

as systems based on rules, 875

and Turing machines, 961

two-dimensional, 1104

unrestricted, 939

Grand unified models (in physics), 1025, 1043

Granular materials

flow in, 1001

packing in, 986

Graph grammars, 1040

Graph isomorphism

and NP completeness, 1146

Graph layout, 193

Graph theory

and discrete packings, 987

and planarity of networks, 1045

Graphical interfaces, 1102

Graphical representation of time, 1031

Graphical user interfaces

as alternative to language, 631

and history of computing, 1108

Graphics

as basis for analysis, 111

production of in this book, 851

Graphics3D

and 3D cellular automata, 927

Graphs

for attractors, 277

cellular automata on, 930, 936

small, 194

see also Networks

Grass

growth of, 1004

and Kant on complexity, 861

Grassmann, Hermann G. (Germany, 1809–1877)

and axioms for arithmetic, 1152

Grassmann algebra

as generalizing numbers, 1168

Gravitational waves

detectors of, 1048

and speed of light, 1041

in vacuum, 536, 1053

Gravitons, 1054

as particles, 1043

and space vs. matter, 1028

Gravity, 530-537

CPT violation in, 1019

in early universe, 1021

history of, 1047

n-body systems subject to, 1021

particle production by, 1062

randomness in systems under, 313

and time and computation, 1130

in ultimate theory of physics, 469

and vacuum fluctuations, 1062

Gray, Alfred (USA, 1939–1998)

and parametric curves, 1009

in Preface, xiii

Gray code, 901

and concatenation sequences, 913

and constraint satisfaction, 984

and math functions, 731

as ordering of CAs, 352, 885

and ordering of Walsh functions, 1073

Gray levels

dithering to get, 1077

Great Chain of Being, 1197

Great circles

as geodesics, 1049, 1050

Great Mosque of Córdoba, 873

Great Pyramid, 874

Great Wall of China, 1187

Greek biology, 1003

Greek embryology, 1010

Greek grammars, 875

Greek mathematics

and labelling in geometry, 1182

and proof, 1149

rules in, 875

Greek mineralogy, 993

Greek number system, 1182

Greek philosophy

and atomism, 876

and complexity, 861

and definition of life, 1178

and extraterrestrial life, 1180

and free will, 1135

and math in science, 859

and universality, 1109

Greek physics

and ultimate theories, 1024

Green, Milton W. (USA, 1926– )

and sorting networks, 1142

Greenberg, James M. (USA, 1940– )

and reaction-diffusion, 1013

Green's functions

for additive systems, 952

for cellular automata, 950

grep

and regular expressions, 958

Grids

cellular automata on, 169

lines at slopes on, 916

superimposing, 613, 1078

visible from space, 1187

Grigorchuk, Rostislav I. (Ukraine/Russia, 1953– )

and intermediate growth groups, 938

GroebnerBasis

and completion algorithms, 1037

and NP completeness, 1143

Gromov, Mikhael L. (Russia/France/USA, 1943– )

in Preface, xiii

and random groups, 938

Ground state

of quantum field theories, 1062

of spin systems, 944

Groupoids, 1171

Groups (mathematical), 1153

and abstraction in math, 792

axioms for, 773

axioms for finite, 1176

and CA conservation laws, 1023

CAs based on, 887, 956

Cayley graphs of, 1032

commutative

see Commutative groups

constraints defining, 945

decidability with commutativity, 1159

emulating Peano arithmetic, 1159

enumeration of, 805

and forcing by axioms, 1172

and gauge theories, 1045

from generators and relations, 1169

inessential incompleteness of, 800

limiting geometry of, 1051

and multiway systems, 938

number of, 945

and operators allowed by axioms, 1172

and particles in physics, 528

PCP and undecidability in, 1139

polyadic, 1171

random, 938

shortest axioms for, 806

and sphere packings, 986

symmetry for lattices, 980

theorems in pure theory of, 1159

undecidability of equivalence of, 1138

universality of, 784, 1159

word problem for, 1141

Growth

as amplifying randomness, 970

of animals, 413-422

of crystals, 369-373

of cyclic tag systems, 96

Eden model for, 331, 978

general constraints on, 1010

general schemes for, 1011

history of studies in biology, 1003

and maintaining flatness, 1007

parametrizations of, 1010

of plants, 400-413

of sheets of tissue, 412

undecidability of continued, 1138

Growth and Form (book), 1004

Growth inhibition

in plant phyllotaxis, 409

in snowflake growth, 370

Growth rates

in computational complexity theory, 1143

and curvature in networks, 533

general theory of, 1162

in multiway systems, 205, 937

and network dimensions, 478, 1030

of number of trivalent networks, 1029

in recursive functions, 908

in substitution systems, 890

in symbolic systems, 897

in Turing machines, 761, 1145

see also Differential growth

Growth rules

for 1D cellular automata, 24

for 2D cellular automata, 928

Growth totalistic rules, 928

Grzegorczyk hierarchy, 906

GUIs (graphical user interfaces), 1103

and history of computing, 1108

Gullies (in landscapes), 1001

Gustatory (taste) sense, 1105

Gusting of wind, 1001