Skip to main content
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