patternMinor
Classification of recursively enumerable sets
Viewed 0 times
enumerableclassificationsetsrecursively
Problem
It's quite easy to show that there are only three recursive sets up to m-equivalence, namely $\emptyset,\{1\},\mathbb N.$ Can we state something "similarly short" for recursively enumerable sets, like there are only 4 recursively enumerable sets up to m-equivalence – $\emptyset,\{1\},K,\mathbb N$ (where $K=\{i\mid\varphi_i(i)\text{ is def.}\}$)? More specifically, is every non-recursive recursively enumerable set m-equivalent to $K$?
Solution
There are lots of these. Even with respect to Turing reducibility (which extends $m$-reducibility: if $A\not\ge_TB$ then $A\not\ge_mB$), the structure of c.e. sets is extremely rich.
That said, constructing an infinite non-recursive r.e. $A$ with $A<_mK$ is significantly easier than constructing one with $A<_T K$. The former was done by Post in 1944 who introduced the notions of creative and simple sets (each of which are necessarily non-recursive), proved that a simple set exists and that $K$ is creative, and proved that no creative set is $m$-reducibile to any simple set; the latter wasn't achieved until a decade later by Friedberg and Muchnik independently, and required a fundamentally new technique (the priority method).
That said, constructing an infinite non-recursive r.e. $A$ with $A<_mK$ is significantly easier than constructing one with $A<_T K$. The former was done by Post in 1944 who introduced the notions of creative and simple sets (each of which are necessarily non-recursive), proved that a simple set exists and that $K$ is creative, and proved that no creative set is $m$-reducibile to any simple set; the latter wasn't achieved until a decade later by Friedberg and Muchnik independently, and required a fundamentally new technique (the priority method).
Context
StackExchange Computer Science Q#133076, answer score: 3
Revisions (0)
No revisions yet.