# Index

H theorem of Boltzmann, 1020

Haar wavelets, 1074

Hackers

and precursors to my work, 879

and universe as computer, 860

Hadamard, Jacques S. (France, 1865–1963)

and chaos theory, 971

and Hadamard matrices, 1073

Hadamard matrices, 1073

Hadamard order

for Walsh functions, 1073

Hadrons

as particles, 1043

in QCD, 1061

Hailstone numbers (3n+1 problem), 904

Hair cells

in inner ear, 585, 1079

Hair follicles

and animal coloration, 1012

Haken, Hermann P. J. (Germany, 1927– )

and reaction-diffusion, 1013

Hales, Stephen (England, 1677–1761)

and leaf growth, 1005

Hales, Thomas C. (USA, 1958– )

and sphere packings, 986

Halftoning, 1077

Halite (rock salt) hopper crystals, 993

Halting

in aggregation systems, 979

in function definitions, 1163

longest times for, 1144

in one-way TMs, 759, 1143

in register machines, 896

in small Turing machines, 1119

in symbolic systems, 897, 897'

in Turing machines, 889

Halting probabilities

and algorithmic randomness, 1067

for code 20, 964

for Turing machines, 1143

and universal objects, 1127

Halting problems, 1137

analog of, 754

axioms for proofs about, 1167

for cellular automata, 1137

and correspondence systems, 1140

and integer equations, 788

in *Mathematica*, 1138

for multiway systems, 1137

and negation, 1158

and oracles, 1126

proofs of undecidability of, 1137

and proving undecidability, 1130

and sets, 1139

in specific axiom systems, 1163

trivial for primitive recursion, 907

for Turing machines, 1137

undecidability of, 1128, 1136

Halton (digit reversal) sequences, 905

Hamiltonian paths

and NP completeness, 1146

trivalent networks with, 1029

Hamiltonians

in discrete quantum systems, 1060

for PDEs, 923

Hamming, Richard W. (USA, 1915–1998)

and error-correcting codes, 1101

Hamming codes, 1101

Hamming distance

and error correction, 1101

and layout of networks, 1031

Hamming weight (DigitCount), 902

Handles on networks, 527, 1045

Handprints

purpose of in cave paintings, 1184

Handwriting

randomness in, 1192

Hankel, Hermann (Germany, 1839–1873)

and generalization in math, 1168

Haploid cells

and randomness in biology, 970

Hard hexagon model

and 2D entropies, 959

as exactly soluble, 1133

Hard sphere gas, 1022

and CA fluids history, 999

CA idealization of, 446

and chaos theory, 971

on inspirational book cover, 864

with stationary scattering, 312

and thermodynamics, 1020

Hard square models (lattice gases), 999

Hardware

for 1D cellular automata, 868

for 2D cellular automata, 928

structure of computer, 1108

Hardy, G. Harold (England, 1877–1947)

and Goldbach's Conjecture, 911

and iterated maps, 919

Harmonic analysis

of substitution systems, 1081

and Walsh functions, 1073

Harmonic analyzer, 1107

Harmonic functions

and flatness in tissue growth, 1007, 1010

Harmonic oscillator

as exactly soluble, 1133

Harmony (musical)

and math thinking, 1177

perception of, 1079

Harmony in nature, 967

Harrington, Leo A. (USA, 1946– )

and unprovable statements, 1163

Hartley, Ralph V. L. (USA, 1888–1970)

and information theory, 1181

Hartman, Hyman (USA, 1936– )

and CA classes, 948

in Preface, xiii

Harvard Mark I computer, 1107

Hashing, 622, 1100

as application of randomness, 1192

to speed up evolution, 1134

Hasse diagrams of posets

and causal networks, 1040

Hasse's algorithm (3n+1 problem), 904

Hasse's Principle

for Diophantine equations, 1165

Hastings, Stuart P. (USA, 1937– )

and reaction-diffusion, 1013

Hauptvermutung (of combinatorial topology), 1051

Hausdorff dimension, 933, 958, 1030

Hawking, Stephen W. (England, 1942– )

and black hole radiation, 1062

Hawking radiation, 1062

and uniform spectra, 988

Hayek, Friedrich A. (Austria/England/USA/Germany, 1899–1992)

and free will, 1135

hcp (hexagonal close packing), 986

Head size

in animal growth, 421

Heads (of expressions), 896

depth of in trees, 897

as type specifications, 898

Hearing, 585-588

of elephants, 1181

human, 1079

Heart (human)

1/f noise in beating of, 969

as excitable medium, 1013

modelling and history of CAs, 878

Hearts of palm, 1004

Heat

analogies with computation, 726

character of, 445

history of theories of, 1019

Heat bath

and 2D Ising model, 982

Heat capacities

and quantum history, 1056

Heat exchangers

geometrical forms of, 1183

Heated fluids

and convection, 1000

Heaven

and form of extraterrestrials, 1191

Heavenly bodies

perfection of, 875

Hebb, Donald O. (Canada, 1904–1985)

and neural networks, 1099

Hebrew religion

and free will, 1135

Hedlund, Gustav A. (USA, 1904–1993)

in Preface, xiii

and shift-commuting block maps, 878

and surjective CAs, 960

Heights of humans

distribution of, 977, 1003

Heighway, John E. (USA, 1930– )

and dragon curves, 893

Heisenberg, Werner K. (Germany, 1901–1976)

and matrix mechanics, 1056

Heliozoan

pattern formed in, 385

Helium

lack of quantum solution to, 1133

randomness in convection of, 976

Helix

in shell models, 1008

Hellman, Martin E. (USA, 1945– )

and math cryptography, 1089

Helmholtz, Hermann L. F. v. (Germany, 1821–1894)

and sound perception, 1080

Henkin semantics (for higher-order logics), 1167

Heptagons

hyperbolic tiling with, 1050

and negative curvature, 532

Herbs

leaf shapes for identifying, 1005

Herds

and randomness in markets, 1015

Heredity

use of simple rules in, 860

HermiteH (Hermite polynomials)

in solution of harmonic oscillator, 1133

Hero (Heron) (Egypt, ~62 AD)

and computing devices, 1107

Heterostructures, 1082

Hewlett-Packard calculators

reverse Polish in, 896

Hexagonal cellular automata

and fluid flow, 378

implementation of, 992

as models of crystal growth, 369

and momentum conservation, 1024

number of rules in, 928

Hexagonal close packing, 986

Hexagonal lattice

of animal pigment cells, 1012

circle packings in, 349, 985

of circles in ornament, 873

of deformable objects, 988

enumeration on, 959

implementation of CAs on, 992

isotropy on, 980

and r=1/2 1D CA, 885

random walks on, 329

and shapes of cells, 1007

Turing machines on, 930

Hexagonal prism, 929

Hexagrams

of I Ching, 893

Hidden Markov models, 590, 1084

Hidden units

in neural networks, 1102

Hidden-variables theories, 543, 1058, 1064

Hierarchies

as avoiding thermodynamics, 453

in computational complexity theory, 1142

and defining complexity, 1069

in embryo development, 419

of function growth rates, 1163

and history of complexity, 862

in probabilistic models, 1084

and randomness in markets, 1015

Higgs field

and expansion of universe, 1055

and notion of ether, 1042

particle associated with, 1047

and particle masses, 1047

High-energy collisions

Monte Carlo simulation of, 968

High-level programming

and programs in notes, 854

High-school algebra

axioms of, 1153, 1153'

Higher-order logics, 1167

Higher organisms

phenomenon of existence of, 398

Highest common factor

see GCD (greatest common divisor)

HighLife (2D class 4 CA), 949

Higman, Graham (England, 1917– )

and axioms for groups, 1153

Hilbert, David (Germany, 1862–1943)

and axioms for geometry, 1154

and character of math, 1176

and Diophantine equations, 1161

and foundations of math, 1149

and general relativity, 1052

and math in science, 859

and metamathematics, 1150

and space-filling curves, 893

and undecidability, 1136

and zeros of zeta function, 918

Hilbert space

in quantum theory, 1059

Hilbert's Tenth Problem, 1161

Hilbert's Thirteenth Problem, 1128

Hill climbing, 346

Hillenbrand, Thomas (Germany, 1970– )

and automated proofs, 1158

Hillman, David (USA, 1955– )

and axioms for logic, 1151

in Preface, xii

Hindu-Arabic number system, 902, 1182

Hindu temples

nesting in, 874

Hinton, Geoffrey E. (England/USA/Canada, 1947– )

and neural networks, 1100

Hippocampus (in brain), 1102

Hippocrates of Chios (Greece, ~460 BC)

and embryology, 1010

Hiss

sound of random sequence, 585

Historians

and free will, 1135

Historical perspectives, 844-846

see also history items in specific entries

History

accidents of in universe, 505

as central to human condition, 846, 1196

of complexity research, 862

computations done in human, 837

of definition of sciences, 863

effect on math of, 792

as explaining axiom systems, 816

general comments about, 850

of life on Earth, 387, 825

of math and ease of concepts, 1177

recorded by physical objects, 1195

role of in biological evolution, 388

theory of and chaos, 971

uniqueness of for universe, 504

History register

see Shift registers

Hobbes, Thomas (England, 1588–1679)

and free will, 1135

and nature of space, 1028

Hodgkin-Huxley equation

as example of PDE, 161

Hofmeister, Wilhelm F. B. (Germany, 1824–1877)

and phyllotaxis, 1007

Hofstadter, Douglas R. (USA, 1945– )

and recursive sequences, 880, 907

Hokusai, Katsushika (Japan, 1760–1849)

and fluid turbulence, 997

Hölder exponents, 959

Holland, John H. (USA, 1929– )

and genetic algorithms, 985

in Preface, xiii

Homoclinic tangles, 972

Homogeneity

origins of, 353

Homogeneous structures

see Cellular automata

Homomorphisms

and generalized additivity, 952

Homoplectic processes (extrinsic randomness generation), 973

Homotopy

and structures in networks, 1046

and topological defects, 1045

Homunculus hypothesis, 1010

Honda, Hisao (Japan, 1943– )

and branching in plants, 1005

Honeycomb

form of, 1011

length minimization in, 988

Hooke, Robert (England, 1635–1703)

and snowflakes, 992

Hopfield, John J. (USA, 1933– )

and neural networks, 1100, 1102

in Preface, xiii

Hopi language

and Sapir-Whorf hypothesis, 1181

Hopper crystals, 993

Horizon problem (in cosmology), 1055

Hormones

in brains, 1099

in plants, 404

Horn shell

growth of, 415

Horner form

and evaluation of powers, 1093

Horns (animal)

as artificial-looking, 828

compared to antlers, 1008

growth of, 413

Horse races

as source of randomness, 968

Horton stream order (in tributaries), 1001

Hours-minutes-seconds

origin of, 902

Hoyle, Fred (England, 1915–2001)

and extraterrestrials, 1190

HP 700

and creation of this book, 854

HP calculators

reverse Polish notation in, 896

Huffman, David A. (USA, 1925–1999)

and data compression, 1069

Huffman coding, 564

adaptive, 1069

implementation of, 1071

and JPEG compression, 1074

Human behavior

and computational irreducibility, 1132

free will in, 750-753, 1135

and game theory, 1104

laws of, 1014

Occam's razor for, 1025

Human condition

defining features of, 1196

scientific approaches to, 845

Human form

parametrizations of, 1010

Human history

vs. biological evolution, 399

Human languages

see Languages (human)

Human relics in archeology, 1183

Human thinking, 620-631

and constructs in math, 1177

emulation by computers of, 733

and Gödel's Theorem, 1159

and Principle of Computational Equivalence, 733, 1130

Human will

see Free will

Humanities

relativism in, 1131

summary of relations to, 9, 863

Humans

artifacts of early, 1184

defining properties of intelligence of, 822

and future technology, 1195, 1196

genetic programs of, 383, 1002

height distributions of, 977, 1003

making randomness, 306, 970

mathematical power of, 1126

as only intelligence, 822

uniqueness of, 844, 1195

visual system of, 577

weight distributions of, 977

Humboldt, F. W. H. Alexander v. (Germany, 1769–1859)

and branching in plants, 1004

Hume, David (Scotland, 1711–1776)

and purposes in nature, 1185

Humidity

and weather, 1177

Huntington, Edward V. (USA, 1874–1952)

and axioms for logic, 1151

Huntington axioms for logic, 773, 1151

Hurwitz numbers, 914

Hydraulic jump, 377

Hydrocarbons

considered interesting, 1194

Hydrodynamics

see Fluid flow

Hydrogen atom

as exactly soluble, 1133

and history of quantum theory, 1056

Hydrology

and forms of landscapes, 1001

Hyena

pigmentation pattern of, 426

Hyperbolic equations, 923, 940

Hyperbolic space, 1049

Hypercube

Boolean, 1095

and trivalent networks, 1029

Hypercycles

and origin of life, 1179

Hyperelliptic Diophantine equations, 1164

Hyperelliptic functions

in solution of spinning top, 1133

Hypergeometric functions

asymptotic behavior of, 917

and continued fractions, 914

and curves from curvature, 1009

and nested patterns, 612

Hypergeometric1F1

in Calogero-Moser model, 1133

Hypergeometric2F1

and caps on hyperspheres, 1050

and quintic equations, 945

in Seiberg-Witten model, 1133

and special functions, 1092

and Thue-Morse sequence, 1092

and trinomial coefficients, 1091

HypergeometricPFQ

and 6j symbols, 1055

difficulty of evaluating, 1134

from rational integral, 916

Hypergraphs, 1029

Hyperreals

as generalizing numbers, 1168

Hypersonic flow

see Supersonic flow

Hypersphere

volume of, 479, 1050

Hyphenation

lack of in this book, 852