Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. A Note on Natural Creative Sets and Goedel Numberings

A Note on Natural Creative Sets and Goedel Numberings

File(s)
80-405.pdf (935.63 KB)
80-405.ps (307.18 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6245
Collections
Computer Science Technical Reports
Hartmanis, Juris
Author
Hartmanis, Juris
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.

Date Issued
1980-01
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR80-405
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance