CP8201: Recommended reading

[BBJ] Boolos, Burgess, Jeffrey "Computability and Logic", 5th edition, Cambridge University Press, 2007.

[EM] Elliot Mendelson "Introduction to Mathematical Logic", 4th edition, published by Chapman & Hall, 1997.

[HE] Herbert Enderton "Computability Theory", 1st edition, published by Elsevier, 2011. Electronic version.

[MBA] Mordechai Ben-Ari "Mathematical Logic For Computer Science", corrected 2nd edition, Springer 2008.

[MD] Martin Davis "Computability and Unsolvability", Dover Publications, 1982.

[PS] Peter Smith "An Introduction to Godel's Theorems", Cambridge University Press, 2007.

[SC] Stephen Cook `` CSC 438F/2404F: Computability and Logic'', Lecture Notes, Fall 2008.

[SS] Stephen Simpson Lecture Notes on Mathematical Logic for MATH557. MATH 557 is an introductory graduate-level course on mathematical logic at Penn State University.

[US] Uwe Schonning "Logic for computer scientists". Publisher Boston : Birkhauser, 1999. Electronic version.

1. September 4: Introduction. Brief review of functions, relations, cartesian products of sets. The primitive recursive (p.r.) functions: basic functions (zero, successor, identity) closed under operations of composition and primitive recursion. Examples: constant functions, addition, multiplication, factorial, signum, truncated subtraction, and so on. The p.r. functions are effectively computable using a sequence of possibly nested "for"-loops. Not all effectively computable functions are p.r.: Cantor's diagonal argument. Introduction to mu-recursive functions. Regular functions. Unbounded "while-do"-loops computing the value of h(x) as the minimal value when a regular function becomes 0 for the first time. Read the handout. Also, read [HE]: Section 1.2.2 (pages 18-22) and Chapter 2, Items 1-11 (pages 29-35). [BBJ]: Chapter 6 [PS]: Chapter 11.


2. September 11: (\mu--)Recursive Functions. a finite sum and product of (primitive) recursive functions are (primitive) recursive. Recursive Sets and Relations: characterisic function. Function defined by cases, substitution of (primitive) recursive functions into a (primitive) recursive relation. Negation, disjunction, conjunction, bounded existential and universal quantification of (primitive) recursive relation(s) is a (primitive) recursive relation. Bounded minimization (maximization) and bounded search. Examples: less-than relation, equality, max(x,y) and min(x,y) function, "m divides n" relation, remainder and quotient, number of divisors relation, prime numbers. Read: [BBJ] Chapter 6 and Section 7.1. [PS]: Chapters 11, 29. [HE]: Sections 2.1, items 9-15, and Section 2.2 (pages 47-49). Examples of Recursive Functions. [EM]: Section 3.3.


3. September 18: Recursively Enumerable Sets. Enumerability using lists and using (general) recursive functions. The methods to prove enumerability: examples. Cantor's zig-zag method for enumerating pairs of positive integers. Base-b encoding. Shuffling of enumerable sets. Prime decomposition. The set of all sets is not enumerable. Diagonalization. [BBJ] Chapters 1 and 2. Encoding string of numbers by a single number using a p.r. encoding function. Decoding function (returns i-th element of the string) is also p.r. Sequence numbers. A p.r. function lh(x) computing the number of the initial non-zero prime factors. Concatenation of strings of natural numbers. Read [HE]: Chapter 2, Section 2.1.1, items 16-24. [BBJ]: Example 7.11. Kleene Normal Form for recursive functions: \mu-minimization is needed only once.


4. September 25: Turing Computability. [EM]: Section 5.1 and [MD]: Sections 1.1 and 1.2. You can read also [BBJ]: Chapter 3.

[SK] Stephen Kleene ``An Introduction to Metamathematics" (any edition).

[RS] Raymond M. Smullyan ``First-Order Logic", Dover, 1995.

1. September 15: Introduction. Review of background [read handout]. Primitive-Recursive Functions. [BBJ]: Chapter 6 [PS]: Chapter 11. [SK]: Section 43.


2. September 22: Primitive-Recursive Functions. Recursive Functions. Recursive Sets and Relations. [BBJ]: Chapter 6 and Section 7.1. [PS]: Chapters 11, 29. Examples of Recursive Functions. [EM]: Section 3.3. [SK]: Sections 44, 45. Dr. Gianluigi Bellin's handout on primitive recursive functions.


3. September 29: Recursive Functions and Relations, examples: [SK] Section 45. The Ackermann-Peter function: [SK] Section 55, [PS] Section 29.3. Kleene Normal Form: [SK] Section 58. Recursively Enumerable Sets. Enumerability. Diagonalization. [BBJ] Chapters 1 and 2.
4. October 6: Turing Computability. [EM]: Section 5.1 and [MD]: Sections 1.1 and 1.2. You can read also [BBJ]: Chapter 3. Side reading (not required): Patrick Hayes and Kenneth Ford Turing Test Considered Harmful, in the proceedings of the International Joint Conference on AI (IJCAI-1995), Montreal Canada, August 20-25, 1995.
5. October 13: Examples of Turing Computable Functions. Basic p.r. functions are Turing computable (successor, zero, identity). [EM]: Section 5.1 and [MD]: Sections 1.2 and 1.3. Read also examples in [BBJ]: Chapter 3.     Enumeration of Turing Machines. Diagonal function is not Turing computable. [BBJ], Chapter 4. [PS]: Sections 33.1 and 33.2


6. October 20: Uncomputability (The Halting Problem). [BBJ], Chapter 4. Theorem: "Every recursive function is Turing computable" (using dextral Turing machines). [PS]: Chapter 32. Theorem: "Every unary Turing computable function is recursive". [BBJ]: Section 8.1. For arbitrary n-place functions see [MD]:Section 4.1 (not required).

   (Extra class on Friday October 23rd) Finish the proof that every unary Turing computable function is recursive. Universal Turing machines. Kleene normal form theorem [BBJ]: Section 8.2. [PS]: Section 33.6.

7. October 27: Semirecursive relations [BBJ] Section 7.2 Recursively enumerable sets [BBJ] Section 8.3 Propositional logic: [RS] Chapter 1 and [MBA] Chapter 2. You can also find all definitions, theorems and many examples in Stephen Simpson's lecture notes on mathematical logic: Read Chapter 1, pages 3-22.


8. November 3 Midterm test (in class). Semantic Tableau: construction. Soundness theorem. [MBA]: Chapter 2. You can also read [RS]: Chapters 2 and 3.


9. November 10. Completeness theorem for semantic tableau. [MBA]: Chapter 2. A brief summary is provided in S.Simpson's lecture notes pages 18-22. Introduction to first order logic. Basic Semantic Definition. [SC] Predicate Calculus, pages 18-22. You can find an excellent introduction to FOL in [EM]: Sections 2.1 and 2.2. You can also read S.Simpson's lecture notes pages 25-30.


10. November 17. Semantics of FOL: satisfiability, logical consequence, validity. Logical equivalence: examples. Note that we used in class the symbol <=> from meta-language to say that sentences A and B are logically equivalent: A <=> B (i.e., A and B have same models). Please use the symbol <-> as the equivalence connective when you write formulas, e.g. (A <-> B), in the FOL "object language". Substitution in terms and in formulas, a term freely substitutable for a variable in a formula, substitution theorem. [SC] Predicate Calculus, pages 23 - 27. Read also Chapter 6 (pages 33-39) from Stefan Bilaniuk's A Problem Course in Mathematical Logic (LaTeX source is available too). There are several related articles in Stanford Encyclopedia of Philosophy, e.g., read Semantics in the entry on classical logic (by Stewart Shapiro) and First-order languages and structures in the entry First-order Model Theory (by Wilfrid Hodges).
    Proofs in FOL. Semantic tableau: examples, Gamma-rules, Delta-rules, systematic construction of semantic tableau, soundness and completeness. Godel completeness theorem for FOL. Read [MBA], Section 5.5. Also, consult Dr. D.Delic's handouts about semantic tableau that he prepared for his undegraduate course MTH714 (Logic and Computability): read Section 2.6 (tableau in propositional logic) and read Section 5.5 (tableau in FOL); you may skip other sections.
    Konig Lemma, Compactness theorem (countable case only). Read [SS], Sections 1.6 & 1.7 (pages 20-21: propositional logic) and Section 2.6 (page 46: FOL).
    Theorem: if a language L is finite, then the set of valid L-sentences is r.e. (i.e., semi-decidable or semi-recursive). Recall a definition of a recursive set and the complementation principle from your lecture notes (see also [BBJ] Section 7.2): a set X is recursive iff both X and the complement of X are r.e.


11. November 24. Read S. Cook's 2006 Notes: Herbrand theorem (pages 51-52, Nonstandard Models). In addition, you might wish to read (not required) H.Enderton's book "A mathematical introduction to logic", Section 3.1 (theory of successor) and Section 3.2 (Presburger arithmetics).
    Also, read Incompleteness and Undecidability: Representing relations by formulas (pages 81-95, but we skipped in class the proof of Exists Delta Theorem because of lack of time) and The Peano Arithmetic theory (PA) (pages 96-99).


12. December 1. Robinson Arithmetics: RA Representation Theorem: pages 99-102. Main Lemma and its Corollaries. Results for Consistent (possibly unsound theories): pages 105-108. Godel's Incompleteness Theorems. Read S. Cook's 2008 Lecture Notes, pp109-112. You can read also S.Simpson's paper Partial Realizations of Hilbert's Program. It was published in 1988 in the Journal of Symbolic Logic, volume 53, pages 349-363 and it is available from S.Simpson's Web page in a various formats. Extra reading: [BBJ], Chapter 18 (not required).

CP8201: Algorithms and Computability.