News for hackers. Stuff that matters.
Re:SQL query to generate the Mandelbrot set as ASCII art by bawolff on Saturday February 22, 2020 @04:04AM (#22390086)
> 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

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.

Re:SQL query to generate the Mandelbrot set as ASCII art by cryptonector on Monday February 24, 2020 @01:04PM (#22406510)
For Turing-completeness you need conditionals and looping. A machine that can loop but has no conditionals wouldn't be a very useful machine. So, yes, what I wrote wasn't exactly correct, but for all practical purposes was correct.