- Edited
...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