Automata and Computability I

Catalog description

Formal models for computability; universal programs; Church's thesis; unsolvable problems and reducibilities; partial recursive functions; recursive and recursively enumerable sets; s-m-n theorem and the recursion theorem.