3 ms·
The simplest way to make something not Turing-complete is to put a bound on the resources it can use. Like giving it limited time and/or memory. So you can hav
by lacker 6y ago
The simplest way to make something not Turing-complete is to put a bound on the resources it can use. Like giving it limited time and/or memory.
So you can have a practical, useful, non-Turing-complete language by forcing every function to have a limit on the number of steps it can take. It can be implicit if you want. In practice, most embedded scripting systems use this route, which is why you don't really need a separate language just for non-Turing-completeness.
- fnrslvr 6y agoThis might get you away from the literal statement of Rice's theorem, but we tend to ask questions about our programs' behaviour across all possible inputs, and these questions tend to remain impossible to solve in general. For example, finding out whether a time-bounded Turing machine outputs 0 all inputs is still undecidable. (coRE-complete, in fact. That's better in some sense than the Pi_2-completeness of the same problem for Turing machines without the time bound, but since neither admits a solution in the form of a computer program, a lot of people would consider the difference an academic curiosity only.)
- Dylan16807 6y ago> For example, finding out whether a time-bounded Turing machine outputs 0 all inputs is still undecidable. Is that a problem? I mean, if you're installing a timeout then haven't you already decided that the answer is "no"?
- fnrslvr 6y agoIf the time bound is being put in place in the hopes of being able to automatically analyze the behaviour of the code, then no. I singled out "outputting 0" on every input because it's among the simplest possible specs you could try try to check with the kind of "very powerful semantic analysis" tool the top-level post was hoping for. In practice you probably want to check a more complex spec -- you want your code to solve a specific problem on whatever input it receives -- but if the "always output 0" spec is impossible to automatically check, then what hope do more relevant specs have?
- a1369209993 6y ago> For example, finding out whether a time-bounded Turing machine outputs 0 all inputs is still undecidable. No it's not; call the time bound N; the TM can only inspect N symbols, so there are 2^N possible inputs; a exhaustive check takes O(N*2^N) operations.
- fnrslvr 6y ago> call the time bound N Call the time bound c|x|^k, where x is the input and c and k are constants. I see what point you're making, and I agree that you get yourself a nice, merely coNP-complete problem if you're willing to cut off the space of inputs at a point by enforcing a constant time bound or whatever. More than anything, this kind of argument makes me shudder at just how hard the very worst stuff in NP must be.
- Dylan16807 6y agoWhen people talk about "limited time and/or memory" for a runtime they're almost certainly talking about something constant, or a small polynomial of the input size. But yes, it should reduce to NP territory. If you actually had a nondeterministic CPU, then for most use cases you could fully evaluate these machines in seconds.
- a1369209993 6y ago> limited time [to] a small polynomial of the input size. This is backwards; I meant that if you have any time bound whatsoever, the number of inputs you can inspect is limited to (a architecture-specific finite multiple of) the number of operations you can execute (because inspecting a input is such a operation).
- Dylan16807 6y agoI wasn't talking about your argument that the calculation is finite. I was talking about how N is chosen in the first place.
- 6y ago