# Turing Machine in SQL (3/5)

This is the third of five posts on this subject.

In previous posts, I have presented how
to implement a Turing Machine (TM) with the tape stored as an `ARRAY`

or in a
separate `TABLE`

accessed through SQL functions.
In this post the solution is more cleanly relational, with the tape contents
stored in a column of the recursive query, very like
Andrew Gierth’s CTS implementation.

## TM with a Window Function

In this post the TM is built from the following SQL features: `WITH RECURSIVE`

to iterate till the machine stops, `INNER JOIN`

to get transition and state
informations, `WINDOW`

functions and `CASE`

expression to extract the next
symbol from the recursive table, two sub-`SELECT`

s to initialize the recursion,
another `CASE`

expression to copy, update and extend the tape, a `CROSS JOIN`

to append blanks at the end of the tape.

An `ARRAY`

, `GROUP BY`

and `ORDER`

are also used to record the tape state, but
is not strictly necessary, it is just there for displaying the TM execution
summary at the end.

## TM Execution

Let us now execute a run with a recursive query:

```
WITH RECURSIVE running(iter, sid, len, pos, psym, tid, tsym) AS (
-- set first iteration at state 0, position 1
SELECT
0, 0,
(SELECT COUNT(*)::INTEGER FROM Turing.Tape),
1, (SELECT symbol FROM Turing.Tape WHERE tid=1),
tid, symbol
FROM Turing.Tape
UNION
-- compute next iteration
SELECT
pr.iter + 1,
tr.new_state,
pr.len,
pr.pos + tr.move,
-- recover next iteration symbol
-- this hack because 'running' cannot be used twice
MAX(CASE WHEN pr.pos+tr.move=pr.tid THEN pr.tsym ELSE NULL END) OVER (),
CASE
-- tape index
WHEN hk.keep THEN pr.tid
-- append a new index
ELSE pr.len + pr.iter + 1
END,
CASE
-- update symbol
WHEN hk.keep AND pr.tid=pr.pos THEN tr.new_symbol
-- or keep previous symbol
WHEN hk.keep THEN pr.tsym
-- append a blank
ELSE 0
END
FROM running AS pr
JOIN -- corresponding transition
Turing.Transition AS tr ON (pr.sid=tr.sid AND pr.psym=tr.symbol)
JOIN -- state information, necessary to know whether to stop
Turing.State AS st ON (tr.sid=st.sid)
CROSS JOIN -- hack to append a 0 at the end of the tape
(VALUES (TRUE), (FALSE)) AS hk(keep)
WHERE -- stop on a final state
NOT st.isFinal
)
-- just stores the computed iterations
INSERT INTO Turing.Run(rid, sid, pos, tape)
SELECT
-- iteration, current state, tape head position
iter, sid, pos,
-- build an array from tape symbols for easier display
ARRAY_AGG(tsym ORDER BY tid ASC)
FROM running
GROUP BY iter, sid, pos
ORDER BY iter;
```

Some comments about this query:

The motivation for the `WINDOW`

function is that Postgres forbids using the
recursive table twice in the query, so this function allows to hide the
additional reference needed to extract the next symbol.
I do not really understand the motivation for this restriction which seems a
little bit artificial.
Possibly it allows some optimisation when iterating on the query, but is also
impairs what can be done with the `WITH RECURSIVE`

construct.
Well, this is consistent with the fact that it iterates only on newly created
rows.

There is also a `CROSS JOIN`

hack for appending a blank symbol to the tape at
each iteration, so that a tape symbol is always found when moving the TM head.

This query basically uses the same tricks as the CTS one, but for the
`OUTER JOIN`

or other `NULL`

handling which are avoided (well, there is a
`NULL`

, but putting -1 would work as well).
ISTM that they are needed for CTS because of the specifics of CTS, namely that a
rule must only be applied when a tape contains 1, or ignored otherwise.

You can try this self-contained SQL script which implements a Turing Machine for accepting the \(A^nB^nC^n\) language using the above method.

In the next post, I show how to get rid of both
`WITH RECURSIVE`

and `WINDOW`

function…