# Turing Machine in SQL (3)

This is the third of five posts [1, 2, 3, 4, 5] on this subject.

In previous posts [1, 2], 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.

## Turing Machine 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.

### Turing Machine 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
-- first, common part is repeated over and over
0, 0,
-- tape length needed to know where to insert blanks
(SELECT COUNT(*)::INTEGER FROM Tape),
-- position and next symbol to consider
1, (SELECT symbol FROM Tape WHERE tid=1),
-- then the tape contents
tid, symbol
FROM Tape
UNION
-- compute next iteration
SELECT
pr.iter + 1,
tr.new_state,
pr.len, -- the initial length could also be recomputed with a sub-query
pr.pos + tr.move,
-- recover next iteration symbol
-- this "hack" because 'running' cannot be used twice in the query
MAX(CASE WHEN pr.pos+tr.move=pr.tid THEN pr.tsym ELSE NULL END) OVER (),
CASE
WHEN hack.keep THEN pr.tid -- tape index
ELSE pr.len + pr.iter + 1 -- append a new index
END,
CASE
WHEN hack.keep AND pr.tid=pr.pos THEN tr.new_symbol -- update symbol
WHEN hack.keep THEN pr.tsym -- or keep previous symbol
ELSE 0 -- or append a blank symbol
END
FROM running AS pr
JOIN -- corresponding transition
Transition AS tr ON (pr.sid=tr.sid AND pr.psym=tr.symbol)
JOIN -- state information, necessary to know whether to stop
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 hack(keep)
WHERE -- stop on a final state
NOT st.isFinal
)
-- just stores the computed iterations
INSERT INTO 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 PostgreSQL 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.

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 *AnBnCn* language using the above method.

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

and `WINDOW`

function…