THINKING ABOUT GÖDEL AND TURING<br> Essays on Complexity, 1970-2007

THINKING ABOUT GÖDEL AND TURING
Essays on Complexity, 1970-2007

CONTENTS


FRONT MATTER Gregory J Chaitin	i
Introductory note Gregory J Chaitin	1
On the difficulty of computations Gregory J Chaitin	3
Information-theoretic computational complexity Gregory J Chaitin	17
Randomness and mathematical proof Gregory J Chaitin	31
Gödel's theorem and information Gregory J Chaitin	47
Randomness in arithmetic Gregory J Chaitin	65
Randomness in arithmetic and the decline & fall of reductionism in pure mathematics Gregory J Chaitin	75
A century of controversy over the foundations of mathematics Gregory J Chaitin	99
A century of controversy over the foundations of mathematics Gregory J Chaitin	129
Metamathematics and the foundations of mathematics Gregory J Chaitin	153
Paradoxes of randomness Gregory J Chaitin	169
Two philosophical applications of algorithmic information theory Gregory J Chaitin	189
On the intelligibility of the universe and the notions of simplicity, complexity and irreducibility Gregory J Chaitin	201
Leibniz, information, math & physics Gregory J Chaitin	227
Leibniz, randomness & the halting probability Gregory J Chaitin	241
Complexity & Leibniz Gregory J Chaitin	247
The limits of reason Gregory J Chaitin	251
How real are real numbers? Gregory J Chaitin	267
Epistemology as information theory: From Leibniz to Ω Gregory J Chaitin	281
Is incompleteness a serious problem? Gregory J Chaitin	299
Speculations on biology, information & complexity Gregory J Chaitin	303
How much information can there be in a real number? Gregory J Chaitin	313
The halting probability Ω: Irreducible complexity in pure mathematics Gregory J Chaitin	319
The halting probability Ω: Concentrated creativity Gregory J Chaitin	333
BACK MATTER Gregory J Chaitin	335
Back