|
|
About this class
Contents
The course focuses on:
- universal models for computation, including Turing machines
- characterizations of computable and semi-computable
problem classes, including presentations of a number of
unsolvable problems, diagonalization, and reduction
- introduction to propositional logic, predicate logic, and
program logic, logical proof systems with applications
(program verification)
- Gödel’s completeness and incompleteness theorems
Goals
The goals of this course are to give the student the following
capabilities:
- to be familiar with the basic terminology for computability and logic
- to describe basic computability classes and fundamental logics
- to describe basic properties of computability classes and logics
- to explain constructive/algorithmic approaches to computability
classes and logics
- to analyse and to prove properties of computability classes and
logics
Lecturer
Mogens Nielsen
Teaching assistants
Course administrator
Course material
The books appearing below are available from Gad Stakbogladen, Naturfag.
Lectures
Wednesday 14 - 17. Auditorium D1 (1531-113).
Prerequisites
Regularity and Automata.
Examination
Oral, 12-scale; two assignments have to be answered
satisfactorily in order to attend the final oral exam
Language
Danish (course material in English)
ECTS
5 ECTS
Quarter
1
|
