3 ms·

"halting is not the property most people care about" I agree that non-Turing complete languages are hugely interesting and likely to be more important as we go

"halting is not the property most people care about" I agree that non-Turing complete languages are hugely interesting and likely to be more important as we go forward. But not for this reason. Most of the non-trivial properties people do care about can be used to tell you if a program is going to halt in a finite amount of time. Want an upper bound on memory? This program doesn't have one? Well, then it never halts. It has one? Well, then we know it halts or loops within 2^bits steps - run it for that many steps and you know which. I think non-Turing-complete will prove interesting because our programs are currently described in Turing complete languages, but run in more constrained contexts anyway. A program that always halts after running for 2^100 steps is not Turing complete. A program that halts if it tries to use more than 2^100 bytes of memory is not Turing complete. Applying these constraints in this way doesn't help us with analysis much, but it hints that we can probably find other ways to constrain our programs which won't get in the way of what we're trying to accomplish, and it's quite possible that some of those will let us build languages more amenable to analysis (and further possible that the gains in analysis will make up for a limited amount of getting-in-the-way).

gugagore 11y ago
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.

gugagore 11y ago

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.