Timeline for answer to The most outrageous (or ridiculous) conjectures in mathematics by Jason Rute
Current License: CC BY-SA 3.0
Post Revisions
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Mar 15, 2017 at 21:35 | comment | added | Noah Schweber | So really what such a construction gets you is a class of intermediate degrees, but no individual intermediate degree. (Incidentally these constructions relativize, as described above, to produce degrees between $0^\alpha$ and $0^{\alpha+1}$ for any (reasonable) $\alpha$.) | |
| Mar 15, 2017 at 21:33 | comment | added | Noah Schweber | @cody No, it does not, at least not in the sense you mean! First of all, there are several different solutions to Post's problem: Friedberg-Muchnik, a low simple set, Sacks density applied to $0<0'$, Kucera's priority-free argument, etc. So right off the bat there's a ton of different constructions. But even focusing on a single one - say, the low simple set construction - things don't get better: the construction begins with a fixed enumeration of the Turing machines, and if you change that enumeration the resulting degree changes as well. (cont'd) | |
| Mar 15, 2017 at 19:46 | comment | added | cody | @NoahSchweber: doesn't the solution to Post's problem give an example of a (non-natural, of course) intermediate degree between $\bf{0}$ and $\bf{0'}$? | |
| Mar 13, 2017 at 15:20 | comment | added | Noah Schweber | (Sorry for the lengthy explanation, hopefully this sort of answered your question and gave some motivation.) | |
| Mar 13, 2017 at 15:20 | comment | added | Noah Schweber | we show that it's hard to give a method for producing things between $0^\alpha$ and $0^{\alpha+1}$. So one good place to look is at problems which don't obviously relativize to higher degrees. E.g. algebraic questions arguably have this character: there is no canonical version of the rationals corresponding to a given noncomputable Turing degree, so there's no reason to believe that Hilbert's 10th for $\mathbb{Q}$ "relativizes" in any good sense, so the mentioned obstacles don't apply. Another potential type of examples is usual Hilbert's 10th, but restricted to ??? Diophantine equations. | |
| Mar 13, 2017 at 15:17 | comment | added | Noah Schweber | So call a "weakly intermediate degree" one which is not of the form $0^\alpha$ for any $\alpha$ (there's actually some dangerous subtlety here, but ignore that for now), and call an "intermediate degree" one which is strictly between $0$ and $0'$. There is currently no known example of a natural weakly intermediate degree, let alone an intermediate degree, there are theorems that finding such a thing would be hard, and there are conjectures that it would be really hard. So where can we look for examples if we're optimistic? Well the feature the hardness results/conjectures use is relativity: | |
| Mar 13, 2017 at 15:13 | comment | added | Noah Schweber | @GilKalai He means "intermediate" in the sense of the Turing degrees. There are lots of natural examples of unsolvable problems about natural numbers (= undecidable sets) - whether a given Diophantine equation has a solution, whether a given Turing machine halts on every input, etc. - but all known examples are equivalent to some iterate of the Halting Problem. Indeed, to a certain extent we can show that there is no "easy" way to always find a Turing degree between $0^{\alpha}$ and $0^{\alpha+1}$. | |
| Feb 7, 2017 at 10:58 | comment | added | Gil Kalai | Dear Jason, can you explain briefly what "intermediate degree" means? | |
| Jan 18, 2017 at 13:54 | comment | added | Gro-Tsen | Whom did you hear suggest that Hilbert's 10th problem for rationals might be an intermediate degree? The idea came to my mind a couple of times, especially after hearing a talk by Poonen on why it seems so difficult to apply the standard approach of reducing to the Entscheidungsproblem. So I'd be curious to know what anyone else thinks on the matter. | |
| Jan 18, 2017 at 3:22 | history | edited | Todd Trimble | CC BY-SA 3.0 |
deleted 1 character in body
|
| S Jan 18, 2017 at 3:18 | history | answered | Jason Rute | CC BY-SA 3.0 | |
| S Jan 18, 2017 at 3:18 | history | made wiki | Post Made Community Wiki by Jason Rute |