Computability
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| NI-VYC | Z,ZK | 4 | 2P+2C | Czech |
- Garant předmětu:
- Jan Starý
- Lecturer:
- Jan Starý
- Tutor:
- Jan Starý
- Supervisor:
- Department of Applied Mathematics
- Synopsis:
-
Classical theory of recursive functions and effective computability.
- Requirements:
-
Elementary arithmetics, a basic course in mathematical logic.
- Syllabus of lectures:
-
1. Introduction. Elementary recursive functions.
2. Primitive recursive functions. Ackermann function.
3. General recursive functions. Universal functions.
4. Partial recursive functions.
5. Turing machines.
6. The power of Turing machines.
7. Universal machine. Halting Problem.
8. The equivalence of Turing machines and recursive functions.
9. Arithmetics: coding the language.
10. Recursive axiomatization.
11. (In)completeness and (un)decidability.
12. Diagonal lemma, Gödel's theorem.
- Syllabus of tutorials:
-
1. Elementary recursive functions.
2. Primitive recursive functions
3. General recursive functions.
4. Partial recursive functions.
5. Turing machines.
6. Programming Turing machines.
7. Programming Turing machines.
8. Programming Turing machines.
9. Gödel coding and decoding.
10. Decidability: examples.
11. Undecidability: examples.
12. Diagonalization.
- 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:
- https://courses.fit.cvut.cz/NI-VYC/
- Time-table for winter semester 2022/2023:
- Time-table is not available yet
- Time-table for summer semester 2022/2023:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Wed Thu Fri - The course is a part of the following study plans:
-
- Bachelor program Informatics, unspecified branch, in Czech, 2015-2020 (elective course)
- Bachelor branch Security and Information Technology, in Czech, 2015-2020 (elective course)
- Bachelor branch Computer Science, in Czech, 2015-2020 (elective course)
- Bachelor branch Computer Engineering, in Czech, 2015-2020 (elective course)
- Bachelor branch Information Systems and Management, in Czech, 2015-2020 (elective course)
- Bachelor branch Knowledge Engineering, in Czech, 2015-2017 (elective course)
- Bachelor branch Web and Software Engineering, spec. Software Engineering, in Czech, 2015-2020 (elective course)
- Bachelor branch Web and Software Engineering, spec. Web Engineering, in Czech, 2015-2020 (elective course)
- Bachelor branch Web and Software Engineering, spec. Computer Graphics, in Czech, 2015-2020 (elective course)
- Bachelor branch Knowledge Engineering, in Czech, 2018-2020 (elective course)
- Master specialization Computer Security, in Czech, 2020 (elective course)
- Master specialization Design and Programming of Embedded Systems, in Czech, 2020 (elective course)
- Master specialization Computer Systems and Networks, in Czech, 202 (elective course)
- Master specialization Management Informatics, in Czech, 2020 (elective course)
- Master specialization Software Engineering, in Czech, 2020 (elective course)
- Master specialization System Programming, in Czech, version from 2020 (elective course)
- Master specialization Web Engineering, in Czech, 2020 (elective course)
- Master specialization Knowledge Engineering, in Czech, 2020 (elective course)
- Master specialization Computer Science, in Czech, 2020 (elective course)
- Mgr. programme, for the phase of study without specialisation, ver. for 2020 and higher (elective course)
- Bachelor specialization Information Security, in Czech, 2021 (elective course)
- Bachelor specialization Management Informatics, in Czech, 2021 (elective course)
- Bachelor specialization Computer Graphics, in Czech, 2021 (elective course)
- Bachelor specialization Computer Engineering, in Czech, 2021 (elective course)
- Bachelor program, unspecified specialization, in Czech, 2021 (elective course)
- Bachelor specialization Web Engineering, in Czech, 2021 (elective course)
- Bachelor specialization Artificial Intelligence, in Czech, 2021 (elective course)
- Bachelor specialization Computer Science, in Czech, 2021 (elective course)
- Bachelor specialization Software Engineering, in Czech, 2021 (elective course)
- Bachelor specialization Computer Systems and Virtualization, in Czech, 2021 (elective course)
- Bachelor specialization Computer Networks and Internet, in Czech, 2021 (elective course)
- Study plan for Ukrainian refugees (elective course)
- Bachelor branch Web and Software Engineering, spec. Computer Graphics, in Czech, Dubin (elective course)