Timeline for Halting problem for bounded length programs
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 16, 2019 at 1:17 | comment | added | Dmitry Krachun | @Gro-Tsen Thanks! It seems like passing to the prefix-free universal computable function will slightly increase the length, though. Or is it possible to do with the length being $O(n)$ where $n$ is the number of states? If you directly do the sum over possible Turing machines summing something like $n^{-10n}$ for each machine that halts, then knowing $O(n\log{n})$ bits of that number should suffice. | |
| Aug 15, 2019 at 23:03 | comment | added | Gro-Tsen | Though the exact asymptotics may need to be checked, it seems to me that your question is answered by the section “Relationship to the halting problem” in Wikipedia's article on Chaitin's constant. | |
| Aug 15, 2019 at 22:11 | history | asked | Dmitry Krachun | CC BY-SA 4.0 |