Timeline for Interesting examples of generic behavior of mathematical objects being either unreasonably structured or simply unreasonable
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 14, 2014 at 13:02 | comment | added | Joel David Hamkins | I think the mentions of P and NP here in regard to the paper may lead to confusion, so let me clarify the matter. The result we prove is that there is a measure-one set of TM programs on which the halting problem is trivial, so trivial that it can be decided in polynomial time (even linear time). This has nothing to do with whether the programs themselves operate in P or NP. But in fact, a corollary of the proof of the result is that almost all programs compute a function with finite domain, using the particular TM formalism of that paper. | |
| May 14, 2014 at 5:01 | comment | added | Kevin Ventullo | @GerhardPaseman I would take it to mean that the set NP \ P has measure zero | |
| May 7, 2014 at 19:37 | comment | added | Joel David Hamkins | OK, I made your suggested edit. | |
| May 7, 2014 at 19:33 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 34 characters in body
|
| May 7, 2014 at 19:29 | comment | added | Gerhard Paseman | I appreciate the edit. It would be even more clear if you said "fall off the beginning of the tape", so that the one-sidedness is evident and the notion of the tape length stays vague (poly-time versus infinite). Gerhard "My Programs Often Stop Themselves" Paseman, 2014.05.07 | |
| May 7, 2014 at 19:24 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 416 characters in body
|
| May 7, 2014 at 19:19 | comment | added | Joel David Hamkins | @GerhardPaseman thanks for the advice; I have added some explanation. | |
| May 7, 2014 at 19:18 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 416 characters in body
|
| May 7, 2014 at 19:14 | comment | added | Gerhard Paseman | You might expand upon this briefly. Just looking at the linked abstract, I get the impression that with probability 1 you can tell if a program will stop in polynomial time, in polynomial time. This might mean that with high probability P is equal to NP. Gerhard "Or Most Programs Are Garbage" Paseman, 2014.05.07 | |
| May 7, 2014 at 19:13 | comment | added | Joel David Hamkins | Yes, as we discuss in the paper, the argument is for the one-way infinite tape models. With two-way infinite tapes, if you allow many halt states, then almost all programs halt very quickly. But if you have a two-way infinite tape and only one halt state, then the best known currently is that proportion $1/e^2$ of all Turing machines fail to halt, for trivial reasons. | |
| May 7, 2014 at 19:09 | comment | added | Benjamin Steinberg | @JoelHamkins, does this not depend on the model of Turing machine? What happens with two-way infinite tapes? | |
| S May 7, 2014 at 18:42 | history | answered | Joel David Hamkins | CC BY-SA 3.0 | |
| S May 7, 2014 at 18:42 | history | made wiki | Post Made Community Wiki by Joel David Hamkins |