Timeline for Halting problem about subclass of Turing Machines
Current License: CC BY-SA 3.0
16 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Aug 20, 2017 at 22:43 | vote | accept | XL _At_Here_There | ||
Aug 1, 2017 at 10:33 | answer | added | anonymous | timeline score: 4 | |
Jul 22, 2017 at 0:56 | comment | added | Eric Astor | @XL_at_China With regards to your question on black holes... I might point you to the final corollary of my paper at arxiv.org/pdf/1405.0022.pdf, which has (as a consequence) that there is an effective enumeration of the TM programs for which the halting problem is not decidable on any set of asymptotic density 1... but I can't name a specific model of computation that produces it naturally, nor do I know that you should find an intermediate measure. | |
Jul 20, 2017 at 16:57 | comment | added | XL _At_Here_There | The answer to the first question depends deeply on computational models | |
Jul 20, 2017 at 13:32 | comment | added | XL _At_Here_There | @JoelDavidHamkins excuse me for disturbing you again, any other articles or materials about "for other models one finds a black hole of some measure intermediate between 0 and 1, rather than measure 0."? | |
Jul 20, 2017 at 13:24 | comment | added | XL _At_Here_There | "The proof, unfortunately, does not fully generalize to all the other implementations of Turing machines, since for other models one finds a black hole of some measure intermediate between 0 and 1, rather than measure 0." cited from other post of Joel | |
Jul 20, 2017 at 12:59 | comment | added | XL _At_Here_There | @JoelDavidHamkins thank you. Some interesting theorems. | |
Jul 20, 2017 at 12:15 | comment | added | Joel David Hamkins | I've made such a post at mathoverflow.net/a/58074/1946. | |
Jul 20, 2017 at 11:54 | comment | added | XL _At_Here_There | @JoelDavidHamkins why not post an simplified one of your article as answer? | |
Jul 20, 2017 at 11:03 | comment | added | Joel David Hamkins | Meanwhile, the halting problem is decidable on a set of TM programs having asymptotic density one, so that as $n$ increases, the fraction of the $n$-state programs in the set goes to $1$. See jdh.hamkins.org/haltingproblemdecidable. | |
Jul 20, 2017 at 4:57 | comment | added | Noah Schweber | @AndreasBlass And of course we can even enlarge it by infinitely many Turing machines, via the padding lemma. | |
Jul 20, 2017 at 4:20 | comment | added | Andreas Blass | If the halting problem is decidable for a subclass of $TM$, then it's also decidable for the slightly larger subclass obtained by adding one more Turing machine (or adding any finite number of Turing machines). | |
Jul 20, 2017 at 3:12 | history | edited | XL _At_Here_There | CC BY-SA 3.0 |
added 1 character in body
|
Jul 20, 2017 at 2:52 | history | edited | XL _At_Here_There | CC BY-SA 3.0 |
edited title
|
Jul 20, 2017 at 2:46 | history | edited | XL _At_Here_There | CC BY-SA 3.0 |
added 39 characters in body
|
Jul 20, 2017 at 2:39 | history | asked | XL _At_Here_There | CC BY-SA 3.0 |