Arithmetic and
Incompleteness
Finalizing the computability half of the course
Theory of Arithmetic
• The theory Th(N) of all the facts about the structure of natural numbers is LIFE
• Naturally there is a desire to capture it through a manageable set of axioms
• By manageable I mean finite, or just computable
• By capture I mean axiomatize
• Sadly, this isn’t possible (Gödel’s Incompleteness Theorem)
Peano Axioms
• A suggested axiomatization for Th(N)
• From those axioms one can deduce (using a formal proof) many facts
about the natural numbers • … but not every fact
Gödel’s First Incompleteness
• Within the language of arithmetic, Gödel used his numbering tricks to make sentences speak about themselves (self reference)
• Theideaistocreateaformula𝑃(𝑥,𝑦)using0,+,×,(,),𝑠,→,¬,…suchthatyis the Gödel number of a proof in PA of the sentence whose Gödel number is 𝑥
• Look now at this sentence: ¬∃𝑦𝑃(𝑒, 𝑦) where 𝑒 = 𝑔𝑛(¬∃𝑦𝑃 𝑒, 𝑦 )
• It says e (myself), not provable
• We see (as outsiders to PA) that it is true, but PA does not
Gödel’s Second Incompleteness
• Gödel decided to play more with his numbering trick and created a sentence that speaks about PA (about the system from within the system)
• The sentence said: PA is consistent
• Consis(PA): ¬∃𝑦𝑃(𝑔𝑛(¬ 0 = 0 ), 𝑦) (there is no proof of 0 ≠ 0)
• Then Gödel showed that: PA ⊬ Consis(PA)
• In other words, PA cannot prove its own consistency
Generalizability of the Incompleteness Theorems
• All those proofs of Gödel just required that the system is powerful enough to express arithmetic
• So, he was able to prove similar facts about, e.g., set theory •0=∅,1= ∅,2= ∅,∅ ,…,𝑛={0,1,…,𝑛−1}
In philosophical terms
• A system which is powerful (enough to describe arithmetic) does not have a decidable list of axioms from which every fact would follow
• Imagine yourself creating a manageable (finite or computable) list of rules (laws) from which everything in your system of interest should follow.
• Unless the system is very weak, we can’t
Peace out Computability
Theory of Complexity
Inside what computers can do
Computation
• Formality produced models of computation: Turing Machines, Recursive Functions
• Other weaker models with restricted memory: Finite Automata, Pushdown Automata
• Turing Machines are a much more accurate model of a general purpose computer
• Church-Turing thesis connects real-world with theory
• Formality enable us to tell what computers can’t do
• Formality made concepts like randomness tangible
• I would like you to take a look at Sipser’s book
Complexity Analysis
• Formality does not only help us tell what computers can’t do, it also allows a general rigorous way to discuss computation resources (time and space)
• What is efficient computation? Turing Machines formalize efficiency and enable measuring it in a standard way
• Time as the number of steps (or transitions). Space as the number of tape cells used.
Complexity Measures
• Time Measure: 𝑡 𝑖, 𝑥 = min{𝑠: 𝜑𝑖,𝑠 (𝑥) ↓}
• Space Measure:
𝑀𝑖,𝑥 =ቐh𝑒𝑎𝑑𝑤h𝑖𝑙𝑒𝑐𝑜𝑚𝑝𝑢𝑡𝑖𝑛𝑔𝜑𝑖,𝑠 𝑥 if 𝜑𝑖,𝑠(𝑥)↓
𝑇h𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐𝑒𝑙𝑙𝑠 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 𝑏𝑦 𝑡h𝑒 𝑟𝑒𝑎𝑑𝑖𝑛𝑔 ↑ otherwise
• Those are examples of complexity measures
• A complexity measure is a more general concept (check Blum Axioms)
Polynomial Time Computability
• A function f is polynomial time computable if:
1. Thereis𝑒suchthat𝑓=𝜑𝑒
2. There is a polynomial 𝑝(𝑛) such that 𝑡 𝑒, 𝑥 ≤ 𝑝(|𝑥|) for every binary string input 𝑥
• Such a function is called tractable, or efficiently computable
We should think in Turing Machine terms
• Since the concepts we are discussing now are mechanical, we switch our terminology from p.c. functions to TMs
• We will work with TMs that halt on all inputs (total). In other words, all our TMs will be deciders
• 𝑡𝑖𝑚𝑒 M, 𝑥 = The number of steps M takes to accept/reject input 𝑥
Determinism vs Nondeterminism
• When a TM is in a given state and reads the next input symbol, we know what the next state will be (determined)
• In a nondeterministic machine, several choices may exist for the next state at any point
• Transition function (Deterministic)
𝛿: 𝑄 × Γ → 𝑄 × Γ × {𝐿, 𝑅}
• Transition function (Nondeterministic) 𝛿⊆(𝑄×Γ)×(𝑄×Γ× 𝐿,𝑅)
Insomereferences:𝛿:𝑄×Γ→𝑃(𝑄×Γ× 𝐿,𝑅 )
Deterministic vs Nondeterministic
• Deterministic is a special case of Nondeterministic
• However, every Nondeterministic TM can be simulated by a Deterministic one (why? Hint: breadth-first search)
Time Complexity
• Let M be a deterministic TM. The running time or time complexity of M is the function 𝑓: N → N where 𝑓(𝑛) is the maximum number of steps that M uses on any input of size 𝑛
𝑓 𝑛 =max 𝑠:𝑀 𝑥 haltsinexactly𝑠steps, 𝑥 =𝑛 =max{𝑡𝑖𝑚𝑒 𝑀,𝑥 :𝑥∈Σ𝑛}
• So, for all input strings 𝑥 of length 𝑛, 𝑀 𝑥 halts within 𝑓 𝑛 steps • We say M runs in time 𝑓 𝑛 , or that M is an 𝑓 𝑛 time TM
Asymptotic Analysis (O notation)
• Running time is often a complex expression
• We usually are only interested in estimating it
• Example:iftherunningtimeis𝑓 𝑛 =6𝑛3+2𝑛2−20𝑛+45,thenwe describe the running time as 𝑂(𝑛3)
• Generally, we write 𝑓 𝑛 = 𝑂(𝑔(𝑛)) if
∃𝑐∃𝑛0 ∀𝑛≥𝑛0,𝑓 𝑛 ≤𝑐𝑔(𝑛)
• 𝑔(𝑛) is said to be an asymptotic upper bound
Example: The sorting problem
• Input:asequenceof𝑛numbers𝑎 ,𝑎 ,…,𝑎 12𝑛
• Output:areordering𝑎′ ,𝑎′ ,…,𝑎′ of𝑎 ,𝑎 ,…,𝑎 suchthat 12′𝑛12𝑛
𝑎′1 ≤𝑎 2 ≤⋯≤𝑎′𝑛
Idea:
Lookat𝑎 .If≤𝑎 ,moveitbefore𝑎 .Soweobtain𝑎 ,𝑎 ,…,𝑎 .Else,leave
21121𝑛 the ordering as it is, look at 𝑎3, and compare it with 𝑎2
…..
• This is known as insertion sorting
Clarification with numbers: Input: 5,2,4,6,1,3
(a) 5,2,4,6,1,3(Atmost1step) (b) 2,5,4,6,1,3(Atmost2steps) (c) 2,4,5,6,1,3(Atmost3steps) (d) 2,4,5,6,1,3
(e) 1,2,4,5,6,3 (f) 1,2,3,4,5,6
• Total number of steps in worst-case scenario = 1+2+…+6
• In general, with input of size 𝑛, it will be 𝑛(𝑛+1) = 𝑂(𝑛2) 2
Complexity Classes
• For any function 𝑓: N → R+, and 𝑛 ∈ N: 𝑇𝐼𝑀𝐸𝑓𝑛 =
{𝐿: 𝐿 is a language decidable by some TM that runs in worst case time 𝑂(𝑓(𝑛))}
𝑆𝑃𝐴𝐶𝐸 𝑓 𝑛 =
{𝐿: 𝐿 is a language decidable by some TM that runs in worst case space 𝑂(𝑓(𝑛))}
The Class P
• 𝑃 = {𝐿: 𝐿 is a language decidable by some polytime TM} )𝑘𝑛(𝐸𝑀𝐼𝑇 𝑘ڂ = 𝑃 Note that •
Polytime Reducibility
• 𝐴 ≤𝑝 𝐵 if 𝐴 ≤𝑚 𝐵 via an m-reduction f which is polytime
• Fact: If 𝐵 is decidable in polytime, and 𝐴 ≤𝑝 𝐵, then A is also decidable in polytime