Recursion Theory
No Thumbnail Available
Date
2012-10-08T06:14:32Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Recursion theory deals with the fundamental concepts on what subsets of natural numbers (or other famous countable domains) could be de ned e ectively and how complex the so de ned sets are. The basic concept are the recursive and recursively enumerable sets, but the world of sets investigated in recursion theory goes beyond
these sets. The notions are linked to Diophantine sets, de nability by functions via recursion and Turing machines. Although some of the concepts are very old, it took until Matiyasevich's great result that Diophantine and r.e. sets are the same that the picture was fully understood. This lecture gives an overview on the basic results and
proof methods in recursion theory.