Please use this identifier to cite or link to this item:
|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.|
|Appears in Collections:||Technical Reports|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.