Computability

Předmět není vypsán Nerozvrhuje se

Kód	Zakončení	Kredity	Rozsah	Jazyk výuky
NIE-VYC	Z,ZK	4	2P+2C	anglicky

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

Classical theory of recursive functions and effective computability.

Požadavky:

Basic course in logic.

Osnova přednášek:

Osnova cvičení:

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.

Cíle studia:

The basic formalizations of an „algorithm“ and elementary questions of computability.

Studijní materiály:

1. Church: An unsolvable problem of elementary number theory

2. Church: A note on the Entscheidungsproblem

3. Davis: Computability and unsolvability

4. Enderton: Elements of Recursion Theory

5. Kleene: Introduction to Metamathematics

6. Rogers: Theory of Recursive Functions and Effective Computability

7. Shoenfield: Mathematical Logic

8. Turing: On computable numbers

Poznámka:

https://courses.fit.cvut.cz/NIE-VYC/

Další informace:

https://courses.fit.cvut.cz/NIE-VYC/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: