Re:SQL query to generate the Mandelbrot set as ASCII art
by kragen on Saturday February 22, 2020 @02:03PM
(#22392653)
I think SQLite could store and retrieve an extremely large amount of data as TEXT even before adding recursive CTEs, and you could do LIKE '%FOO' || BAR || 'BAZ%' queries to retrieve substring data from them; nevertheless, as far as I know, you couldn't encode Turing-complete queries in a SQL query before recursive CTEs.
Conditional looping is not strictly necessary if you're willing to accept an infinite loop with a "halted" flag set as halting. Moreover, conditional looping and unbounded storage is not strictly sufficient; the loop needs to be able to depend on an unbounded part of the unbounded storage, for example, although not necessarily within a single iteration (which is impossible in many Turing-complete models of computation). So, for example, a finite automaton that stores matched parts of its input string on an output printout, but cannot consult that printout, does not thereby achieve Turing-completeness. Moreover, nondeterministic pushdown automata with ε-productions have conditional looping and unbounded storage that they can actually consult during computation, but they are not Turing-complete; they can only recognize context-free languages.
I don't think you can reduce Turing-completeness to a laundry list of language features in that way, because you can always construct an automaton that restricts the ways those features can be combined so as to avoid Turing-completeness.
This is not, as it may seem, merely a perverse form of computational masochism; on the contrary, it is often considered highly undesirable for a program to unexpectedly enter an infinite loop or perform an arbitrary computation for an attacker, and this is in constant tension with our desire to make our systems simultaneously more powerful, more general and flexible, and less complicated. So work like Meredith Patterson's Language-Theoretic Security and Turner's Total Functional Programming represents important advances in the kinds of systems we can practically build.
Conditional looping is not strictly necessary if you're willing to accept an infinite loop with a "halted" flag set as halting. Moreover, conditional looping and unbounded storage is not strictly sufficient; the loop needs to be able to depend on an unbounded part of the unbounded storage, for example, although not necessarily within a single iteration (which is impossible in many Turing-complete models of computation). So, for example, a finite automaton that stores matched parts of its input string on an output printout, but cannot consult that printout, does not thereby achieve Turing-completeness. Moreover, nondeterministic pushdown automata with ε-productions have conditional looping and unbounded storage that they can actually consult during computation, but they are not Turing-complete; they can only recognize context-free languages.
I don't think you can reduce Turing-completeness to a laundry list of language features in that way, because you can always construct an automaton that restricts the ways those features can be combined so as to avoid Turing-completeness.
This is not, as it may seem, merely a perverse form of computational masochism; on the contrary, it is often considered highly undesirable for a program to unexpectedly enter an infinite loop or perform an arbitrary computation for an attacker, and this is in constant tension with our desire to make our systems simultaneously more powerful, more general and flexible, and less complicated. So work like Meredith Patterson's Language-Theoretic Security and Turner's Total Functional Programming represents important advances in the kinds of systems we can practically build.