3 ms·
True, but all such limitations serve to give an upper bound on the iteration count (which may not be a single constant but depend on the input). It can be demon
by anewvillager 7y ago
True, but all such limitations serve to give an upper bound on the iteration count (which may not be a single constant but depend on the input). It can be demonstrated that if you don't have an upper bound then the language is Turing complete.
- kragen 7y agoYou are speaking in such a sloppy way that I doubt that the reasoning you intend to express is sound; certainly what you have actually said is false. For example, a machine with only the instructions JMP, HLT, and NOP can express loops with no upper bound, but is not Turing-complete; it is computable in linear time whether a given program will halt or not. A more interesting kind of automaton that includes unbounded loops is a nondeterministic finite automaton, which can generate regular languages, but is not Turing-complete. It is true that you do not need to add very many constructs from the programming languages we're familiar with before you reach Turing-completeness; Fractran and Minsky's two-counter machine are two rather astonishing examples. But when we were talking about languages lacking an indefinite-looping construct, we were already outside the bounds of "ordinary programming languages", so we can't just take for granted our vague intuitive ideas of what other things they can do; we have to be specific, not vague, in order to make rigorous statements like "the language is Turing complete."