Algorithms, Logic and Complexity (Reiknirit, rökfræði og reiknanleiki), Spring 2014

Covered material in the textbook for exam

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

Material by chapters:

Chapter 1:
Sets, functions and enumerability [ the whole chapter ]
Chapter 2:
Diagonalization, nonenumerable sets [ the whole chapter ]
Chapter 3:
Turing computability [ the whole chapter ]
Chapter 4:
Uncomputability, the Halting problem, the productivity function [ the whole chapter ]
Chapter 5:
Abacus machines, simulating Abacus machines by Turing machines, recursive functions can be computed by Abacus machines [ the whole chapter ]
Chapter 6:
Recursive functions and primitive recursive functions [ the whole chapter ]
Chapter 7:
Recursive sets and relations [ 7.1-7.2 ]
Chapter 8:
Coding Turing computations, universal Turing machines [ 8.1-8.2 ]
Chapter 9:
First-order logic, the syntax of first-order logic [ 9.1-9.2 ]
Chapter 10:
The semantics of first-order logic, metalogical notations [ 10.1-10.2 ]
Chapter 11:
The undecidability of first-order logic [ 11.1 to middle of page 130 ]

hh (hja) hi.is, April 7th, 2014.