Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

So how is the state space then much smaller than modern memory limits? That still ignores my second point, namely that the logical reasoning that the xyzzyz somehow implied that programs that have state spaces smaller than modern memory limits are in practice analyzeable for halting/not halting, is not sound.

I can tell you now that your code terminates. The set s is strictly increasing in size, inevitably going towards an OOM condition if the loop doesn't terminate by other means. Note that we are talking about determining halting or not halting, not with which value the program halts.

This is not a troll. You tried to respond with something witty. I just pointed out that in this case things like the collatz conjecture don't apply, because it is a conjecture over all natural numbers. When you are working with finite memory, there is no way to encode this conjecture into a program (e.g. by making it halt if the conjecture is true and making it loop when the conjecture is false).



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: