Timeline for Is deciding whether a Turing machine *provably* runs forever equivalent to the halting problem?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 22, 2013 at 16:37 | answer | added | François G. Dorais | timeline score: 5 | |
| May 22, 2013 at 4:33 | vote | accept | Scott Aaronson | ||
| May 22, 2013 at 3:17 | comment | added | François G. Dorais | Ah, I guess your promise problems are what computability theorists call mass problems? | |
| May 22, 2013 at 3:16 | answer | added | Joel David Hamkins | timeline score: 25 | |
| May 22, 2013 at 3:15 | comment | added | Scott Aaronson | François: Yes, I know that CG is not a set; rather, it's what you call a separation problem and what complexity theorists would call a promise problem (the promise being that M halts). But the notion of Turing-reducibility can be generalized to promise problems in a fairly straightforward way, and once you do that $CG\le_T PROVELOOP$ becomes meaningful. Your last observation, implying that in fact $CG\lt_T PROVELOOP$, is quite interesting and not something I knew -- thanks for that! | |
| May 22, 2013 at 3:05 | comment | added | François G. Dorais | Note that GC is not a well-defined set and so $GC \leq_T PROVELOOP$ is not meaningful. There are many solutions to the separation problem, some of which are $<_T HALT$ while others are way up in the stratosphere. What you have shown is that PROVELOOP computes a separating set and is therefore not computable since the separation problem has no computable solution. In fact, it is known that if $X$ is a solution to the separation problem, then there is another solution $Y$ such that $0 <_T Y <_T X$. So there is a solution to the separation problem which is $<_T PROVELOOP$. | |
| May 22, 2013 at 2:53 | answer | added | Noah Schweber | timeline score: 4 | |
| May 22, 2013 at 2:16 | history | edited | Scott Aaronson | CC BY-SA 3.0 |
added 13 characters in body
|
| May 22, 2013 at 2:11 | history | edited | Scott Aaronson | CC BY-SA 3.0 |
added 203 characters in body
|
| May 22, 2013 at 2:03 | history | asked | Scott Aaronson | CC BY-SA 3.0 |