SQL query to generate the Mandelbrot set as ASCII art

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.

He starts by generating a table where each cell is represented by a data structure that enumerates all of the legal values in that cell. The options. Then there is code that can find all the peers of a cell (same row, same column, same square).

Turns out that most 'easy' and many 'moderate' puzzles can be solved by starting with a list of all cells with one option.

For each cell:

* solve the cell

* for all peers, eliminate that value from their options

* for all peers with one remaining option, recurse

I believe that's quadratic time, and intuition tells me breadth-first converges faster.

After that, Norvig reaches for brute force, under the theory that this has already gotten you so close to the solution that it's not worth implementing and debugging more complex constaint logic. But I think that despite his claims that Sudoku is a disease, I think this is a taunt; it simply encourages you to go into a more sophisticated process of elimination.

Single elimination: Any option that only has one cell in a row, column or square: solved.

Double elimination: If a pair of peers have only the same two options, then eliminate that option from all of their common peers. Solves nothing, but may solve other cells.

Triple and Quadruple elimination: same thing, but progressively rarer.

Quintuple elimination: I don't recall why, but it was asserted that since this is more than half of 9, any time this happens a simpler constraint is also true.

I believe that covers all of the moderate difficulty puzzles and the occasional hard ones. From there there's a whole array of other constraints you can implement. You can either do it yourself as an exercise, or there are whole websites dedicated to these rules.

The poster I originally responded to was curious about the speed with which 9x9 Sudoku can be solved despite "its" NP-completeness, and my point was that it's because of the small restriction of the general, truly NP-complete problem, and not because of anything inherently special about the SQL-based solver.

Basically there is only one unique solution to the top row under a different strict ordering. But, you can do a related mapping for a given problem to reduce the table by 9!.

This is actually not true. Behold, a cyclic tag system in SQL:2003-conformant SQL:

http://wiki.postgresql.org/wiki/Cyclic_Tag_System

Here's a blog diving into more detail: http://blog.coelho.net/database/2013/08/17/turing-sql-1.html

Although this is less strictly conforming.

The original thread was in the context of SQLite, which is trivially of equivalent computational power.

However, again: you should probably use Prolog.