Algorithms, Logic and Complexity (Reiknirit, rkfri og reiknanleiki), Spring 2014

Planned syllabus from the textbook

Textbook: Computability and Logic, 5th ed. by George S. Boolos, John P. Burgess and Richard C. Jeffrey.


Weeks 1-2:
Introduction, basic concepts, enumerability, diagonalization [Chapters 1-2]
Weeks 3-4:
Turing machines, Turing computability, uncomputable problems [Chapters 3-4]
Week 5:
Abacus machines and Abacus computability [Chapter 5]
Weeks 6-7:
Recursive functions, recursive sets [Chapters 6-7]
Weeks 8-9:
Church's thesis, equivalence of computation models [Chapter 8]
Weeks 10-12:
First-Order logic, syntax and semantics [Chapters 9-10]
Week 13-14:
Undecidability of First-Order logic [Chapter 11]

hh (hja), January 2014.