Timeline for Accelerating semidecision of halting problem
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 26, 2024 at 12:07 | vote | accept | Trebor | ||
| Jul 21, 2024 at 4:07 | comment | added | ruakh | @DanielWagner: Re: "you can loop this process indefinitely to get an arbitrary speedup": Not necessarily. Consider a sequence like $n^{2.1}, n^{2.01}, n^{2.001}, n^{2.0001}, ...$; each iteration gives you an asymptotic speedup, but you'll never reach $O(n^2)$. | |
| Jul 21, 2024 at 2:13 | comment | added | Daniel Wagner | Suppose we could speed up the decision asymptotically for every (halting) program. Now do the usual trick in this space: take your sped-up decision process, and feed it to itself. You get another asymptotic speedup for free, and you can loop this process indefinitely to get an arbitrary speedup. Sounds unlikely to me (though admittedly there is a lot of formalization work before I'd consider this a "proof"). | |
| Jul 20, 2024 at 15:57 | answer | added | Elegia | timeline score: 4 | |
| Jul 19, 2024 at 22:31 | answer | added | ruakh | timeline score: 2 | |
| Jul 19, 2024 at 21:40 | history | became hot network question | |||
| Jul 19, 2024 at 16:46 | answer | added | BearAqua the Logician | timeline score: 1 | |
| Jul 19, 2024 at 15:44 | comment | added | rus9384 | While you can detect an infinite family of halting machines faster than just with simulating them, I doubt it significantly changes even the average time complexity of the algorithm. The machines that can be detected this way (primitive recursive machines in general) run for time much much less than $BB(n)$. | |
| Jul 19, 2024 at 12:52 | history | asked | Trebor | CC BY-SA 4.0 |