Skip to content


Turing Machine in SQL (4/5)

This is the fourth of five posts on this subject.

In previous posts, I have presented different ways of implementing a Turing Machine (TM) in SQL with Postgres. All three techniques rely on WITH RECURSIVE to iterate till the TM stops, so as to provide some kind of while construct.

In this post, I get rid of this construct, so that the solution does not require Postgres 8.4 or later. Obviously there is a trick: I will use a recursive SQL function with side effects on a TABLE to execute the TM.

Turing Machine in SQL (1/5)

This is the first of five posts on this subject.

Postgres implementation of SQL is Turing Complete, as show by Andrew Gierth on Postgres wiki, where a Cyclic Tag System (CTS), which is proven Turing-complete, is implemented using WITH RECURSIVE, a WINDOW function, CASE conditional expressions and an OUTER JOIN. Although the proof is sound, there is a long path from a CTS to an actual Turing Machine (TM).

The first question I want to answer is: how to build a Turing Machine with SQL only?

The second question I would like to investigate is: What SQL features are actually required to build a relational Turing Machine. For instance, can it be done without WITH RECURSIVE, WINDOW functions and OUTER JOIN? (Teaser for later posts: yes!)

Postgres Warm-up

A database can take some time to reach good performances, the time necessary to OS and database caches to load the necessary data from the hard disk drive. Here is an example with Postgres, which outlines the long delay incurred (18 minutes), presents a simple model to explain this behavior, and shows how to reduce it significantly (to a few minutes).