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 β 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–[2016])
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

Grape leaves, 401, 1006

Graph-based systems, 193–203

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 art, 43, 873

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