Please use this identifier to cite or link to this item: https://dl.comp.nus.edu.sg/handle/1900.100/3842
Title: Recursion Theory
Authors: STEPHAN, Frank
Issue Date: 8-Oct-2012
Series/Report no.: ;TR10/12
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.
URI: http://hdl.handle.net/1900.100/3842
Appears in Collections:Technical Reports

Files in This Item:
File Description SizeFormat 
TR10-12.pdf663.51 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.