Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2018/2019

Computability

The course is not on the list Without time-table
Code Completion Credits Range Language
MI-VYC Z,ZK 4 2+2 Czech
Lecturer:
Jan Starý (guarantor)
Tutor:
Jan Starý (guarantor)
Supervisor:
Department of Applied Mathematics
Synopsis:

Classical theory of recursive functions and effective computability. Recursive functions, Turing machines,

and their equivalence. Church's thesis.

Universal machine, normal form.

Halting Problem and fixed points.

Relations to logic: (in)completeness and (un)decidability.

Requirements:

Basic notions of set theory (relations, functions, orderings) and elementary properties of natural numbers,

programming experience. A basic course in logic is an advantage.

Syllabus of lectures:
Syllabus of tutorials:
Study Objective:

The basic formalizations of an „algorithm“

and elementary questions of computability.

Study materials:

Church: An unsolvable problem of elementary number theory

Church: A note on the Entscheidungsproblem

Davis: Computability and unsolvability

Enderton: Elements of Recursion Theory

Kleene: Introduction to Metamathematics

Rogers: Theory of Recursive Functions and Effective Computability

Shoenfield: Mathematical Logic

Turing: On computable numbers

Černý: Výpočty I

Note:
Further information:
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2019-04-22
For updated information see http://bilakniha.cvut.cz/en/predmet3315506.html