Re:SQL query to generate the Mandelbrot set as ASCII art
by anewvillager on Friday February 21, 2020 @10:13PM
(#22389165)
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.
[ Parent
| on HN ]
Re:SQL query to generate the Mandelbrot set as ASCII art
by kragen on Saturday February 22, 2020 @01:50PM
(#22392571)
You 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."