How to simplest Turing Machine works on postgreSQL
Tags: postgres, database, computerscience, sql
Published: 2019-02-07 11:28:03

---
title: How to simplest Turing Machine works on postgreSQL
published: true
description: 
tags: postgreSQL, database,Computer Science,SQL
---

# version

postgres:10.6

```
postgres=# SELECT version();
 PostgreSQL 10.6 (Ubuntu 10.6-0ubuntu0.18.04.1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0, 64-bit
```


# Preface

I found interesting post about SQL is Turing complete.

http://blog.coelho.net/database/2013/08/17/turing-sql-1.html

This site try to emulate Turing machine on SQL.

This is table definition.

```sql
CREATE TABLE State(    -- TM states
  sid INTEGER PRIMARY KEY,    -- 0 is always the initial state
  isFinal BOOLEAN NOT NULL,
  sname TEXT UNIQUE NOT NULL -- just for show
);

CREATE TABLE Symbol( -- TM symbols
  cid INTEGER PRIMARY KEY,  -- 0 is always the blank symbol
  cname TEXT UNIQUE NOT NULL
);

CREATE TABLE Transition( -- TM transition function
  sid INTEGER NOT NULL REFERENCES State,     -- initial state
  symbol INTEGER NOT NULL REFERENCES Symbol, -- & symbol
  UNIQUE(sid, symbol),
  new_state INTEGER NOT NULL REFERENCES State,
  new_symbol INTEGER NOT NULL REFERENCES Symbol,
  move INTEGER NOT NULL CHECK(move=-1 OR move=1)
);

CREATE TABLE Tape( -- TM initial tape contents
  tid INTEGER PRIMARY KEY,
  symbol INTEGER REFERENCES Symbol
);

```

This is execution query.

```sql
WITH RECURSIVE running(rid, sid, tape, pos) AS (
  -- first store initial tape contents
  SELECT 0, 0, ARRAY(SELECT symbol FROM Tape ORDER BY tid), 1
  UNION
  -- then proceed to compute iterations
  SELECT p.rid+1, t.new_state,
         -- build updated tape as an array
         p.tape[1:p.pos-1] ||                      -- prefix
           t.new_symbol ||                         -- updated cell
           p.tape[p.pos+1:array_length(p.tape,1)], -- suffix
         -- move cursor position
         p.pos+t.move
  FROM running AS p
  -- get state details, to know whether to stop
  JOIN State AS s ON (p.sid=s.sid)
  -- get corresponding state transition
  JOIN Transition AS t ON (t.sid=p.sid AND
                           -- coalesce defaults to blank
                           t.symbol=COALESCE(p.tape[p.pos],0))
  WHERE -- stop on a final state
        NOT s.isFinal
)
-- just store the computed table
INSERT INTO Run
  SELECT * FROM running;
```

But It didn't work with queries in that site only.


```
ERROR:  insert or update on table "run" violates foreign key constraint "run_sid_fkey"
DETAIL:  Key (sid)=(0) is not present in table "state".
```

Because this post has only the table definition(create statement) and no machine data(insert statement)

So I need data of Turing Machine.

>note:I found out later that CTS(Cyclic Tag System) data is written here.
https://wiki.postgresql.org/wiki/Turing_Machine_(with_recursive)

#  (2,3) Turing machine

This time,I choose most simplest Turing machine called "Wolfram's 2-state 3-symbol Turing machine"

https://www.wolframscience.com/prizes/tm23/technicaldetails.html

This Turing machine has 2 satate({1,2}) and 3 Symbol({2,1,0}).



```
{state, color} -> {next_state, next_color, offset(header position)}

{1, 2} -> {1, 1, -1},
{1, 1} -> {1, 2, -1},
{1, 0} -> {2, 1, 1 },
{2, 2} -> {1, 0, 1 },
{2, 1} -> {2, 2, 1 },
{2, 0} -> {1, 2, -1}
```

I check this on paper, and make DB record.

![paper](https://thepracticaldev.s3.amazonaws.com/i/le17719ubwywslrlct1s.jpg)



```sql
INSERT INTO State VALUES(0,FALSE,1),(1,FALSE,2); 
INSERT INTO Symbol VALUES(0,'0'),(1,'1'),(2,'2');
INSERT INTO Transition VALUES
(0,2,0,1,-1),
(0,1,0,2,-1),
(0,0,1,1, 1),
(1,2,0,0, 1),
(1,1,1,2, 1),
(1,0,0,2,-1)

INSERT INTO Tape VALUES(0,0);
```

(2,3)Turing machine don't have halt state.

>Note that there is no halt state for this Turing machine.


Execution query assumes the existence of a halt state,I need change execution query.

```sql
WITH RECURSIVE running(rid, sid, tape, pos) AS (
  -- first store initial tape contents
  SELECT 0, 0, ARRAY(SELECT symbol FROM Tape ORDER BY tid), 1
  UNION
  -- then proceed to compute iterations
  SELECT p.rid+1, t.new_state,
         -- build updated tape as an array
         p.tape[1:p.pos-1] ||                      -- prefix
           t.new_symbol ||                         -- updated cell
           p.tape[p.pos+1:array_length(p.tape,1)], -- suffix
         -- move cursor position
         p.pos+t.move
  FROM running AS p
  -- get state details, to know whether to stop
  JOIN State AS s ON (p.sid=s.sid)
  -- get corresponding state transition
  JOIN Transition AS t ON (t.sid=p.sid AND
                           -- coalesce defaults to blank
                           t.symbol=COALESCE(p.tape[p.pos],0))
  WHERE -- stop on a final state
        --NOT s.isFinal -- There is no halt state.
        NOT p.rid = 100 -- By changing this number 
                        -- you can set the number of generations of cellular automata on tape.
)
-- just store the computed table
INSERT INTO Run
  SELECT * FROM running;
```

# Result

Execution result is here.


rid | sid |            tape             | pos
-----+-----+-----------------------------+-----
  0 |   0 | {0}                         |   1
  1 |   1 | {1}                         |   2
  2 |   0 | {1,2}                       |   1
  3 |   0 | {2,2}                       |   0
  4 |   1 | {1,2,2}                     |   1
  5 |   1 | {2,2,2}                     |   2
  6 |   0 | {2,0,2}                     |   3
  7 |   0 | {2,0,1}                     |   2
  8 |   1 | {2,1,1}                     |   3
  9 |   1 | {2,1,2}                     |   4
 10 |   0 | {2,1,2,2}                   |   3
... | ... | ...                         | ...
 89 |   0 | {2,2,1,1,2,2,2,1,2,2,1,2}   |   2
 90 |   0 | {2,1,1,1,2,2,2,1,2,2,1,2}   |   1
 91 |   0 | {1,1,1,1,2,2,2,1,2,2,1,2}   |   0
 92 |   1 | {1,1,1,1,1,2,2,2,1,2,2,1,2} |   1
 93 |   1 | {2,1,1,1,1,2,2,2,1,2,2,1,2} |   2
 94 |   1 | {2,2,1,1,1,2,2,2,1,2,2,1,2} |   3
 95 |   1 | {2,2,2,1,1,2,2,2,1,2,2,1,2} |   4
 96 |   1 | {2,2,2,2,1,2,2,2,1,2,2,1,2} |   5
 97 |   1 | {2,2,2,2,2,2,2,2,1,2,2,1,2} |   6
 98 |   0 | {2,2,2,2,2,0,2,2,1,2,2,1,2} |   7
 99 |   0 | {2,2,2,2,2,0,1,2,1,2,2,1,2} |   6
100 |   1 | {2,2,2,2,2,1,1,2,1,2,2,1,2} |   7


full version is "result.txt" on my github repository

https://github.com/yuyabu/2state-3color-turing-machine-on-sql

I convert "tape" column to image on this rule.

```
2 -> orange
1 -> yellowfins
0 -> white
```

and after all, I made this cell automaton image.

![automaton](https://thepracticaldev.s3.amazonaws.com/i/pl5xlghhdqu6nrbh2gqt.png)

Although the method of complementing the white cell is different, it is misaligned, but it is almost the same image as wolfram's page's.

# next time

I'll try to make rule 60. Transition function of rule 60 is on NKS book.

```
{{1, 2} -> {2, 2, 1}, {1, 1} -> {1, 1, 1}, {1, 0} -> {3, 1, -1}, {2, 2} -> {2,1, 1}, {2, 1} -> {1, 2, 1}, {3, 2} -> {3, 2, -1}, {3, 1} -> {3, 1, -1}, {3, 0} -> {1, 0, 1}}
```

https://www.wolframscience.com/nks/notes-11-12--rule-60-turing-machines/

This article is translated from my blog post(original is japanese).
http://yuyubu.hatenablog.com/entry/2019/01/15/SQL%E4%B8%8A%E3%81%A72%E7%8A%B6%E6%85%8B3%E8%A8%98%E5%8F%B7%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3%E3%82%92%E3%82%A8%E3%83%9F%E3%83%A5%E3%83%AC%E3%83%BC%E3%82%B7