|
|
|
||
|
Enumerable functions, possible definitions, properties. Recursive and recursively enumerable sets and semirecursive predicates. Time and space complexity.
Last update: T_KNM (19.05.2008)
|
|
||
|
The course gives students a knowledge of enumerable and recursive functions. Last update: T_KNM (19.05.2008)
|
|
||
|
Davis M.: Computability and unsolvability. Mc Graw Hill, N.Y., 1958 Rogers H. jr.: Theory of recursive functions and effective computability. Mc Graw Hill, N.Y., 1967 Last update: T_KNM (19.05.2008)
|
|
||
|
Lectures in a lecture hall. Last update: T_KNM (19.05.2008)
|
|
||
|
Examination according to the syllabus. Last update: T_KNM (19.05.2008)
|
|
||
|
Enumerable functions, their properties, equivalence of their various mathematical definitions. Recursive and recursively enumerable sets and predicates.
Turing Machines' ability to compute all recursive functions. Recursive functions, primitive recursive functions, predicates and sets. Emulation of Turing Machine by primitive recursive functions and predicates. Kleene's theorems. Semirecursive predicates. Predicates that are not recursive. Predicates that are not semirecursive. Creative and simple functions. Last update: T_KNM (19.05.2008)
|
|
||
|
There are no special entry requirements. Last update: T_KNM (19.05.2008)
|
|
||
|
tento předmět se již nevyučuje Last update: Jákl Vojtěch, RNDr. (24.02.2016)
|