Timeline for What is the shortest program for which halting is unknown?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Mar 28, 2017 at 21:24 | history | edited | coudy | CC BY-SA 3.0 |
Replaced double-backslash with a single-backslash.
|
| S Mar 28, 2017 at 21:24 | history | suggested | jeq | CC BY-SA 3.0 |
Replaced double-backslash with a single-backslash.
|
| Mar 28, 2017 at 21:04 | review | Suggested edits | |||
| S Mar 28, 2017 at 21:24 | |||||
| Sep 21, 2012 at 21:03 | comment | added | Kaveh | @Daniel, If you prove the statement for $n_0$ then by the definition of $n_0$ it would follow for all. | |
| Mar 10, 2011 at 17:27 | comment | added | Daniel Litt | Well this is a bit of a quibble, but my claim is that given a correct value, one can produce a proof--on the other hand, Emil's "value" does not allow one to produce a proof. Instead, it produces something silly like "If there is an odd perfect number, let $x$ be that number; otherwise, let $x$ be a proof that there is no odd perfect number." In any case, I think we all understand each other and pretty much agree that the proof technique I "suggest" is essentially useless. | |
| Mar 10, 2011 at 16:44 | comment | added | Andreas Blass |
Emil's statement looks to me entirely parallel to the claim in the question. Emil says to check $n_0$ but gives you no clue how to find it. The claim in the question says to check all halting programs up to a certain length but gives you no clue how to determine which programs those are.
|
|
| Mar 10, 2011 at 16:32 | comment | added | Daniel Litt | This is obviously not the intent of my claim; if you can show me a Turing machine which, given $P$, prints a correct (numerical) value of $n_0$, however, I'll be pretty impressed. Of course, such a machine would solve the halting problem. | |
| Mar 10, 2011 at 12:15 | history | answered | Emil Jeřábek | CC BY-SA 2.5 |