Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: A Note on Natural Creative Sets and Goedel Numberings
Authors: Hartmanis, Juris
Keywords: computer science
technical report
Issue Date: Jan-1980
Publisher: Cornell University
Abstract: Creative sets (or the complete recursively enumerable sets) play an important role in logic and mathematics and they are known to be recursively isomorphic. Therefore, on the one hand, all the creative sets can be viewed as equivalent, on the other hand, we intuitively perceive some creative sets as more "natural and simpler" than others. In this note, we try to capture this intuitive concept precisely by defining a creative set to be natural if all other recursively enumerable sets can be reduced to it by computationally simple reductions and show that these natural creative sets are all isomorphic under the same type of computationally simple mappings. The same ideas are also applied to define natural Goedel numberings.
Appears in Collections:Computer Science Technical Reports
Hartmanis, Juris

Files in This Item:

File Description SizeFormat
80-405.pdf935.63 kBAdobe PDFView/Open
80-405.ps307.18 kBPostscriptView/Open

Refworks Export

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


© 2014 Cornell University Library Contact Us