|
Load:
|
1. komponenta
| Lecture type | Total |
| Lectures |
45 |
* Load is given in academic hour (1 academic hour = 45 minutes)
|
|
Description:
|
COURSE AIMS AND OBJECTIVES:
Introduce students to basic computability theory, enable them to think mathematically about algorithms, develop a few models of computation and motivate Church-Turing's thesis, prove the most important results about undecidability and semidecidability (such as Church's theorem about the undecidability of first-order logic).
COURSE DESCRIPTION AND SYLLABUS:
We introduce the numeric model of computation through imperative programming according to Shoenfield. We describe the procedure of flattening (inlining) and the implementation of the function call. We also introduce LOOP-machines according to Schöning.
We show an alternative model through functional programming according to Kleene. We construct a compiler of partial recursive functions into RAM-programs, proving Kleene's normal form theorem for partial recursive functions.
We introduce the textual model of computation through Turing machines according to Sipser. We virtualize Turing machines inside RAM-machines, proving equivalence of numeric and textual computation. We describe elements of parsing theory.
We introduce lambda-calculus according to Barendregt, as well as the ideas of reduction and expansion. We realize techniques of programming and data representation using lambda-terms. We describe programming paradigms through association with evaluation order. We state the Church-Rosser's theorem.
We generalize obtained results about equivalency of computational models through Church-Turing's thesis, and we prove non-existence of an algorithm for various famous problems such as Entscheidungsproblem. We sketch the proof of Gödel's first incompleteness theorem.
We prove four great theorems of metaprogramming: parameter theorem, recursion theorem, fixpoint theorem and Rice's theorem.
We formalize semi-decidability as recursive enumerability and we characterize it as projection of a decidable relation, as well as through the intuition of waiting for the computation to stop, graphs of computable functions... in the numeric as well as in the textual computation model.
|
|
Literature:
|
-
Komputonomikon - izračunljivost za računarce, Čačić.
-
Izračunljivost - predavanja, Vuković.
-
Recursion Theory, Shoenfield.
-
Introduction to the Theory of Computation, Sipser.
-
Interpreter za lambda-račun, Lovnički.
-
LOOP-izračunljivost, Avirović.
-
Izračunljivost na skupovima Z, Q, R i C, Posavčević.
|
|
Prerequisit for:
|
Enrollment
:
Attended
:
Calculation models
Attended
:
Mathematical logic
Examination
:
Passed
:
Calculation models
Passed
:
Mathematical logic
|
Pristupačnost
