Timeline for What are the most attractive Turing undecidable problems in mathematics?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 18, 2020 at 14:05 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question has been bumped anyway)
|
| Jun 25, 2013 at 3:02 | review | Late answers | |||
| Jun 26, 2013 at 18:02 | |||||
| Mar 28, 2012 at 20:59 | comment | added | Joel David Hamkins | Yes, thank you. This was precisely the point of my challenge, to find out if there are any natural examples of such intermediate degrees, particularly c.e. such degrees. All known such degrees are the result of these kind of complicated constructions aimed specifically at producing such intermediate degrees. But it could be that there are natural sets of natural numbers that happen to have intermediate degree. (For example, how about the set of differences of primes $p-q$?) It is, I believe, a major open question to find such natural instances of intermediate Turing degrees. | |
| Mar 28, 2012 at 18:29 | comment | added | Asher M. Kach | To clarify, Friedberg and Muchnik's introduction of the "finite injury method" solved Post's Problem of the existence of intermediate computably enumerable degrees. The existence of (non-computably enumerable) intermediate degrees was known before Friedberg and Muchnik via the "finite extension method" of Kleene and Post. | |
| Mar 28, 2012 at 17:54 | history | answered | Cody | CC BY-SA 3.0 |