Mathematics – Logic
Scientific paper
2007-01-31
Mathematics
Logic
PhD thesis, 101 pages
Scientific paper
It is possible to enumerate all computer programs. In particular, for every partial computable function, there is a shortest program which computes that function. f-MIN is the set of indices for shortest programs. In 1972, Meyer showed that f-MIN is Turing equivalent to 0'', the halting set with halting set oracle. This paper generalizes the notion of shortest programs, and we use various measures from computability theory to describe the complexity of the resulting "spectral sets." We show that under certain Godel numberings, the spectral sets are exactly the canonical sets 0', 0'', 0''', ... up to Turing equivalence. This is probably not true in general, however we show that spectral sets always contain some useful information. We show that immunity, or "thinness" is a useful characteristic for distinguishing between spectral sets. In the final chapter, we construct a set which neither contains nor is disjoint from any infinite arithmetic set, yet it is 0-majorized and contains a natural spectral set. Thus a pathological set becomes a bit more friendly. Finally, a number of interesting open problems are left for the inspired reader.
No associations
LandOfFree
Noncomputable Spectral Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Noncomputable Spectral Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Noncomputable Spectral Sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-457278