4 ms·

I don't know where this thinking gets us. My computer, once I disconnect it from the internet, is actually a finite state machine and not a Turing machine, whic

I don't know where this thinking gets us. My computer, once I disconnect it from the internet, is actually a finite state machine and not a Turing machine, which I think you acknowledge. How does that help with anything? If my program uses one kebibyte of memory -- no I/O and harddrive, then it loops or halts within 2^(2^10) steps. For me to detect that, in general I need to store a history of length 2^(2^10), which is more than 10^300. That's 10^301 bytes that I need to detect if a 1kb RAM program loops.

dllthomas 11y ago
It is a proof that we can get what we need to done in a language that is not Turing complete. The hope would be that there is some sweet spot we can find wherein we can say things that are dramatically more useful than "it will finish inside 2^(2^100) steps" without impacting usability tremendously more than "it won't use more than a kebibyte of memory" - which is already enough to defang the theoretical objection.