Turing

August 29, 2013
in Postgres, Turing, SQL
3 min read

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.

August 26, 2013
in Postgres, Turing, SQL
4 min read

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.

August 23, 2013
in Postgres, Turing, SQL
3 min read

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.

August 20, 2013
in Postgres, Turing, SQL
4 min read

Turing Machine in SQL (2/5)

This is the second of five posts on this subject.

In a previous post I presented how to implement a Turing Machine (TM) with an ARRAY to store the tape contents. This solution is not really relational, so in this post I’ll show how to build a TM with SQL-only functions.

August 17, 2013
in Postgres, Turing
7 min read

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