Title: Theory / Unimportant / Math / Logic / Chaitin;
Tags: computer_to_instruction hasNotNewEffectReturnsMeaning FromInstruction algoToProg algoToProblem declaration effectToImplementation hasSeenConjDef

Name: A formal axiomatic system
Definition: is consistent
Page: 4
Section: 1
Kind: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Definition2: is complete
Conjdef: An axiomatic system which
Definition3: with a decision problem

Name: A consistent axiomatic system
Definition: One which does not prove \(A\) and \(\neg A\)
Page: 4
Section: 1
Kind: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS

Name: A complete axiomatic system
Definition: One which does prove either \(A\) or \(\neg A\), for all sentence \(A\)
Page: 4
Section: 1
Kind: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS

Page: 4
Effect: Input: a sentence
Output: whether it holds
Section: 1
Extra: Problem
Name: A decision problem
Kind: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS

Smaller0: \(S\) is a consistent axiomatization of natural arithmetic
Greater0: \(S\) is incomplete
Page: 6
Section: 2
Variables: \(S\) an axiomatic system
Kind: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Name: Godël incompleteness theorem

Smaller0: \(S\) is a consistem axiomatization of arithmetic
Greater0: \(S\) does not have a decision procedure
Page: 7
Section: 2
Variables: \(S\) an axiomatic system
Kind: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Name: Turing theorem

Question: How to define an uncountable number ?
Answer: Consider the sequence \((T_i)_{i\in\mathbb N}\) Turing machines outputing binary digits. Let \(d_{i,j}\) the \(j\)-th digit outputted by machine \(i\), or \(0\) if undefined.
Takes the number \((1-d_{i,i})_{i\in\mathbb N}\)
Page: 10
Section: 2
Kind: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS

Name: Chaitin's \(\Omega\)
Definition: \(\sum_{p\text{ halts}}2^{-|p|}\) for \(p\) Turing Machines
Page: 11, 12
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 3
Intuition: The probability that a random program halts
Typ: An absolutely real number in \((0,1)\)
Assuming: No extension of a program is a valid program

Name: An algorithmically incompressible real
Definition: A real whose first \(N\) bit are not printed by a program with less than \(N\) states
Page: 13
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 3

Name: A normal number
Definition: A real \(r\in(0,1)\) such that for each word \(w\) over alphabet \(\{0,\dots,b-1\}\) the proportion of occurrences of \(w\) in the \(b\)-ary expansion of \(r\) of length \(n\) tends to \(\frac{1}{b^{|w|}}\) when \(n\to\infty\)
Page: 14
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 3
Variables: \(b\in\mathbb N^{>1}\)

Name: An absolutely normal number
Definition: A number normal in each base
Page: 14
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 3

Name: Champernowne's number
Definition: The concatenation of the decimal expension of \(n\), for each \(n\in\mathbb N\)
Page: 15
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 3
Property: Normal in base 10

Question: The number of bit of axioms required to prove the value of the \(n\) first bits of \(\Omega\)
Answer: \(n\) minus a constant
Page: 16
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 3

Name: Diophantine equation
Definition: A polynomial with an arbitrary number of variables, and integral coefficients
Page: 19
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 4

Page: 19
Effect: Given a Diophantine equation, decide whether it has a solution ?
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 4
Extra: problem
Name: Hilbert's ten problem

Name: Exponential Diophantine equation
Definition: Diophantine equation where variables can occur in the exponents.
Page: 20
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 4

Question: undecidability in arithmetic
Answer: There exists an exponential Diophantine equation with a parameter \(K\) which have an infinite number of solution iff \(n\)'s bit of \(\Omega\) is 1
Page: 21
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 4

Name: Experimental mathematics
Definition: Considering theorems by testing whether their holds on many values
Page: 25
Chapter: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS
Section: 5

Name: Berry's paradox
Definition: The first positive integer that you can't name in a billion words.
Page: 40
Chapter: ELEGANT LISP PROGRAMS

Instruction: (foo_1 ... foo_n)
Page: 31
Effect: The list containing the n elements foo_i
Chapter: ELEGANT LISP PROGRAMS
Extra: prog

Instruction: (define
  (bar foo_1 ... foo_n)
buz
)
Page: 33
Meaning: Define a function bar with parameters foo__i, whose body is buz
Language: Lisp
Chapter: ELEGANT LISP PROGRAMS
Identifier: bar
Typ: function taking n arguments
Extra: prog

Instruction: (if foo bar buz)
Page: 33
Effect: If foo holds then bar else buz
Chapter: ELEGANT LISP PROGRAMS
Extra: prog

Instruction: 'foo
Page: 34
Effect: State that foo should not be evaluated
Chapter: ELEGANT LISP PROGRAMS
Extra: prog

Instruction: lambda (foo_1 ... foo_n) bar
Page: 34
Effect: A function, with parameters foo_1 ... foo_n and body bar
Chapter: ELEGANT LISP PROGRAMS
Extra: prog

Instruction: car
Page: 34
Effect: Sends a pair to its first element
Context: lisp
Chapter: ELEGANT LISP PROGRAMS
Extra: prog

Instruction: cdr
Page: 34
Effect: The method sending a pair to its second element
Context: Lisp
Chapter: ELEGANT LISP PROGRAMS
Extra: prog

Instruction: nil
Page: 34
Effect: abbreviation for the empty list
Chapter: ELEGANT LISP PROGRAMS
Extra: prog

Name: An elegant LISP expression
Definition: A LISP expression with the property that no smaller expression has the same value.
Page: 35
Chapter: ELEGANT LISP PROGRAMS

Question: The set of provable elegant lisp expression
Answer: contains only elements whose size is 410 plus the LISP complexity of \(F\)
Page: 38
Chapter: ELEGANT LISP PROGRAMS
Variables: \(F\) a formal lisp system

Instruction: Eval
Page: 39
Effect: Given a LISP expression, evaluate it
Chapter: ELEGANT LISP PROGRAMS
Extra: prog

Instruction: Try
Page: 39
Effect: Given a time limit and a LISP expression, evaluate it, halts after this time
Chapter: ELEGANT LISP PROGRAMS
Extra: prog

Question: Difference between Godel and Turing's theorem ?
Answer: Turing consider decision algorithm while Godel consider axiomatization
Page: 7
Section: 2
Kind: RANDOMNESS IN ARITHMETIC AND THE DECLINE AND FALL OF REDUCTIONISM IN PURE MATHEMATICS