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.
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.
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
Top comments (0)