Recursion Theory
| dc.contributor.author | STEPHAN, Frank | en_US |
| dc.date.accessioned | 2012-10-08T06:14:32Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:06Z | |
| dc.date.available | 2012-10-08T06:14:32Z | en_US |
| dc.date.available | 2017-01-23T07:00:06Z | |
| dc.date.issued | 2012-10-08T06:14:32Z | en_US |
| dc.description.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. | en_US |
| dc.format.extent | 679435 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/3842 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | ;TR10/12 | en_US |
| dc.title | Recursion Theory | en_US |
| dc.type | Technical Report | en_US |