Timeline for What is the shortest program for which halting is unknown?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 8, 2021 at 7:28 | comment | added | user21820 | Hello! Sorry this is a bit off-topic, but I would like to know your opinion on whether PA decides Collatz or not, and what evidence you happen to know of that informs your belief. I feel that it's likely that PA decides Collatz, because it seems simple enough to fall under "decidable small cases", analogous to how PA can prove the outputs of the busy beaver function on small inputs. However, I have completely zero evidence, whether mathematical or empirical, for my guess. So I would like to hear your opinion, if you don't mind. Thanks! =) | |
| Jun 29, 2010 at 19:51 | comment | added | Daniel Litt | Definitely, it looks fantastic. Wish I could accept that comment as an answer as well. | |
| Jun 29, 2010 at 19:49 | comment | added | Carl Mummert | I think you will find the paper I posted above interesting. | |
| Jun 29, 2010 at 19:47 | comment | added | Daniel Litt | Ah sorry I was unclear. I'm not suggesting a definition of complexity that is independent of language--just that the length of "translators" provides a bound on the difference between the two complexities. Essentially, my second question was asking whether there is any less trivial relationship (and aiming towards applications, whether we can pick a language in a tricky way to make the method for proof I suggest at all reasonable). | |
| Jun 29, 2010 at 19:43 | comment | added | Carl Mummert | To do that, you still must start with a "preferred" description language, and the complexity will depend on which one you think of as preferred. Perhaps the one I prefer assigns some function to index 0, while your preferred one assigns that function only much larger indices. | |
| Jun 29, 2010 at 19:24 | comment | added | Daniel Litt | This is true, but somehow a very naive answer--if we include the length $p$ of a "translator" program into our analysis of the dependence of length on description language, the dependence is a little less arbitrary. That is, any program in language 1 of length $x$ gives a program of length $p+x$ in language $2$. | |
| Jun 29, 2010 at 19:18 | history | answered | Carl Mummert | CC BY-SA 2.5 |