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."
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."