Timeline for Relation between Turing degrees and functions computable with them
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2014 at 7:34 | vote | accept | Wojowu | ||
| Nov 22, 2014 at 7:34 | comment | added | Wojowu | Interesting, so there are degrees such that some function of this degree isn't bounded by computable function, but there is no dominant function, and e.g. low c.e. sets have this property. | |
| Nov 21, 2014 at 22:52 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 443 characters in body
|
| Nov 21, 2014 at 22:48 | comment | added | Noah Schweber | Further, note that "$B$ hyperimmune" does not imply that $B$ computes a function dominating every computable function. To show this, it suffices to (a) prove Martin's domination theorem (this is the theorem of Bjorn's answer), and then (b) construct a non-high noncomputable c.e. degree via any of the standard arguments (the construction of a low simple set is probably fastest). | |
| Nov 21, 2014 at 22:43 | comment | added | Noah Schweber | (Quibble: all nonzero c.e. degrees are hyperimmune.) | |
| Nov 21, 2014 at 22:42 | comment | added | Noah Schweber | Two further comments. First, note that there are absolutely no dependencies between the three notions of "most:" the sets $\{$1-randoms$\}$, $\{$1-generics$\}$, and $\{$computing 0'$\}$ are large only in the measure, category, and cone senses, respectively. Second, and more interestingly, the fact that - in this case - the r.e. degrees reflect "analytic mostness" is a phenomenon which only happens some of the time. For example, comeager and measure 1-many degrees fail to compute a complete consistent theory extending PA, but there are such degrees which are c.e. | |
| Nov 21, 2014 at 22:39 | comment | added | Noah Schweber | Yes, that seems correct. It's worth noting that there are three common senses of the word "most" in computability theory - comeager, measure 1, and "on a cone." Generally, properties which imply computability-theoretic strength fail for comeager- and measure 1-many sets, but hold on a cone (this last bit is usually quite trivial to prove; it amounts to "strength is preserved upwards"): so, for example, the set of reals computing some fixed (uncomputable) $X$ is measure 0 and is meager, but of course holds on the cone above $X$. Hyperimmunity is a strength property, so it follows this pattern. | |
| Nov 21, 2014 at 20:12 | comment | added | Wojowu | So let me get this straight - if there is $A$-computable function which isn't bounded by any computable function, then degree of $A$ is hyperimmune, and "most" of degrees are hyperimmune, in particular all recursively enumerable degrees are hyperimmune. Is this right? | |
| Nov 21, 2014 at 19:02 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 201 characters in body
|
| Nov 21, 2014 at 18:55 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 201 characters in body
|
| Nov 21, 2014 at 18:43 | history | answered | Noah Schweber | CC BY-SA 3.0 |