Skip to content

Stuff about Things

Postgres Archeology

In a previous post I have ported a Turing Machine (TM) in SQL down to Postgres 7.3.

I report here my fruitless attempts at running previous versions of Postgres on a Debian or Ubuntu Linux. They would not configure and/or compile, at least with the minimal effort I was ready to undergo: writing portable-to-the-future system-dependent C code does not work. Basically, the code from 15 years ago is lost unless you run it on a system from 15 years ago, which may require a hardware from 15 years ago as well, or maybe a VM.

Turing Machine in SQL (5/5)

This is the last of five posts on this subject.

In a previous post I have shown how to build a Turing Machine (TM) in SQL with Postgres using a recursive SQL function. I claimed that this would work with versions of Postgres older than 8.4. In this post, I actually investigate this claim, porting the script down to version 7.3 on a Debian Linux. Testing the relatively simple SQL script with older versions reminds us of all the goodies that have been added over the years.

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