...Because there are still people who don't realise or believe that SQL is a Turing-complete (aka computation universal) language capable in principle of performing any computation performable by a computer. The changes made in the 1999 and 2003 standards changed that. Twenty years ago. So I wrote a single SQL SELECT statement that simulates a Turing machine just to prove it can be done.

Caveats and request for improvement

Now, there are a couple of PostgreSQL-specific points in this code: the array_remove and array_append functions, and there may be one or two places where PostgreSQL's handling of the language is more orthogonal than standard SQL allows. I'm not sure for two reasons: (1) I wanted to be able to actually run the query, and (2) I wasn't going to fork out hundreds of dollars to get a copy of the current standard with which to check just for this purpose. But if these drawbacks could be addressed I'm interested.

Specification.

The tape has two symbols: marked and blank. It is represented in the SELECT by a standard SQL array that lists the positions of marked squares. The machine itself has a state and a position. If the machine's position is in the tape array, then its read/write head is currently "scanning a marked square", otherwise the square it's scanning is blank.

The initial state of the machine (0, 0, 0, ARRAY[]) represents time, starting state, starting position and starting tape contents. If you want to start with a nonempty tape, list the positions of marked squares in the given array.

The rules are 5-tuples (oldstate, ismarked, writemark, move, newstate). Looking at the machine's current state and whether it's scanning a marked square, oldstate and ismarked identify which rule applies. At each step, the machine performs three actions specified by the matching rule: (a) mark the current square (TRUE) or blank it (FALSE), (b), move one square either right (TRUE) or left (FALSE), and (c) either enter a new state or (if newstate is NULL), halt. All three are done on each step (so no "stay put" or "leave the square alone" actions).

newstate being NULL indicates a halting state because there are no rows in the rule table with a corresponding NULL for oldstate. No matching rows in the rule table mean no new rows generated in the machine table to drive further matches. Any value that isn't matched by any oldstate could be used, but using NULL makes it obvious.

The tick field is not important to operation and could be removed. It remains here so that (a) a trace of the entire computation can be obtained by using ORDER BY tick, as done here (the alternative would be to use WHERE state IS NULL to get the final tape configuration), and (b) to force-halt the machine if it runs too long (debugging infinite loops is "fun").

The all-important code

The example rule table takes a positive integer written in unary (e.g. …☐☐☐☐🗹🗹🗹☐☐☐☐…), with the machine starting somewhere off to its left, and doubles it (so, …☐☐☐☐🗹🗹🗹🗹🗹🗹☐…).

WITH RECURSIVE ruletable(oldstate,ismarked,writemark,move,newstate) AS (
	VALUES
 (0,FALSE,FALSE,TRUE,0),
 (0,TRUE,FALSE,TRUE,1),
 (1,FALSE,TRUE,FALSE,2),
 (1,TRUE,TRUE,TRUE,1),
 (2,FALSE,FALSE,TRUE,3),
 (2,TRUE,FALSE,TRUE,4),
 (3,FALSE,TRUE,TRUE,NULL),
 (3,TRUE,TRUE,TRUE,3),
 (4,FALSE,TRUE,FALSE,5),
 (4,TRUE,TRUE,TRUE,4),
 (5,FALSE,TRUE,FALSE,2),
 (5,TRUE,TRUE,FALSE,5)
),
machine(tick,state,position,tape) AS (
	-- Fill in the initial state of the tape in this array
	-- Since ARRAY[] is type-ambiguous, an empty tape needs casting
	(VALUES (0, 0, 0, CAST(ARRAY[5,6,7] AS integer[])))
	UNION ALL
	SELECT
		machine.tick + 1,
		ruletable.newstate,
		machine.position + (CASE WHEN ruletable.move THEN 1 ELSE -1 END),
		CASE WHEN ruletable.writemark
	         THEN array_append(array_remove(machine.tape, machine.position), machine.position)
	         ELSE array_remove(machine.tape, machine.position) END
	FROM machine, ruletable
	WHERE machine.state = ruletable.oldstate
	  AND ruletable.ismarked = (machine.position = ANY(machine.tape))
--	  AND machine.tick < 100 -- "fun"
) SELECT * FROM machine ORDER BY tick
    6 days later
    Write a Reply...