DEV Community

yuyabu
yuyabu

Posted on

How to simplest Turing Machine works on postgreSQL

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.

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.

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

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.

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

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

Discussion (0)