3 ms·

Of course. You can easily build programs too difficult to prove terminate using CTEs. But even before CTEs, SQLite3 was Turing complete: you could write recur

Of course. You can easily build programs too difficult to prove terminate using CTEs. But even before CTEs, SQLite3 was Turing complete: you could write recursive triggers. Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness.

kragen 7y ago
> Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness. There are other ways to restrict looping constructs other than literal max iteration counts to avoid Turing-completeness; structural induction in Coq, LEAN, and Total Functional Programming is one example.
- 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 ago
    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."
bawolff 7y ago
> Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness. I'm not a computability theory person, but that doesn't sound right. Afaik, linear bounded automata can loop infinitely, but are not turing complete. Edit: After googling. I guess the important bit is conditional looping and unbounded storage. I think including recursive triggers is cheating a bit because the impressive bit is the query itself is turing complete without any other setup. But anyways CTEs don't just provide looping, they also provide a means to store and retrieve an unbounded amount of intermediate values. Its not obvious to me that that was possible in single query in sql without CTEs
- kragen 7y ago
  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.

kragen 7y ago

> Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness. There are other ways to restrict looping constructs other than literal max iteration counts to avoid Turing-completeness; structural induction in Coq, LEAN, and Total Functional Programming is one example.

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

bawolff 7y ago

> Recursion == looping. Any looping construct, recursive or otherwise, that doesn't require a literal max iteration count implies Turing completeness. I'm not a computability theory person, but that doesn't sound right. Afaik, linear bounded automata can loop infinitely, but are not turing complete. Edit: After googling. I guess the important bit is conditional looping and unbounded storage. I think including recursive triggers is cheating a bit because the impressive bit is the query itself is turing complete without any other setup. But anyways CTEs don't just provide looping, they also provide a means to store and retrieve an unbounded amount of intermediate values. Its not obvious to me that that was possible in single query in sql without CTEs

kragen 7y ago
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.