SQL上で2状態3記号チューリングマシンをエミュレーションする

SQLがチューリング完全かどうかは、意見が別れていると思いますが、

SQLや、ループの書けない表計算マクロなどもチューリング完全ではない。

一般的にはwith recursive句が導入されたことによって再帰クエリが実行できるようになり、チューリングマシンをSQLでシュミレートできるようになったので、　チューリング完全になったという風になっています。

で、今回実際にSQL上でチューリングマシンをエミュレートしてみようという挑戦になります。

blog.coelho.net

こちらのエントリにチューリングマシンのテーブル定義がありますが、動かすためのチューリングマシンのデータ(状態、シンボル、遷移関数)が無かったので、現在発見されているもっとも単純な万能チューリングマシンであるWolfram's 2-state 3-symbol Turing machineを利用しました。

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

(2,3)TMは遷移関数は全部で6個

f:id:yuyubu:20190115201437j:plain — (2,3)Turing Machine

凡例:{state, color} -> {state, color, offset}

{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}

です。

データをいれます。適当に紙に起こして自分で考えながら書き起こしました。なお本データは(2,3)Turing machineのものですが、このブログ)にあるCTSでも可能かと思います。

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,2,2, 1),
(1,0,0,2,-1)


INSERT INTO Tape VALUES(0,0);

以下がチューリングマシンを動かすクエリです

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 p.rid = 100
)
-- just store the computed table
INSERT INTO Run
  SELECT * FROM running;

(2,3)Turing machineは終了状態がないため、100回目の処理終了時でストップするように条件を書き換えています。

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
 11 |   0 | {2,1,1,2}                   |   2
 12 |   0 | {2,2,1,2}                   |   1
 ・・・・・・・・・・・・・・・・・・・・・・・・・・・
 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

これをビジュアライズしたい。とりあえず桁を揃えてごにょごにょした。

1,0,0,0,0,0,0,0,0,0,0,0,0
1,2,0,0,0,0,0,0,0,0,0,0,0
2,2,0,0,0,0,0,0,0,0,0,0,0
1,2,2,0,0,0,0,0,0,0,0,0,0
2,2,2,0,0,0,0,0,0,0,0,0,0
・・・・・・・・・・・・・・・
2,2,1,1,2,2,2,1,2,2,1,2,0
2,1,1,1,2,2,2,1,2,2,1,2,0
1,1,1,1,2,2,2,1,2,2,1,2,0
1,1,1,1,1,2,2,2,1,2,2,1,2
2,1,1,1,1,2,2,2,1,2,2,1,2
2,2,1,1,1,2,2,2,1,2,2,1,2
2,2,2,1,1,2,2,2,1,2,2,1,2
2,2,2,2,1,2,2,2,1,2,2,1,2
2,2,2,2,2,2,2,2,1,2,2,1,2
2,2,2,2,2,0,2,2,1,2,2,1,2
2,2,2,2,2,0,1,2,1,2,2,1,2
2,2,2,2,2,1,1,2,1,2,2,1,2

で結果できたのがこの画像。若干桁揃えのルールが違うため、同じ形状にならなかったが、wolframのサイトの画像とほぼ同一ものもが得られた。(チューリングマシンがエミュレートできた？)

f:id:yuyubu:20190108202637p:plain — 2 3 チューリングマシンの1~100世代後のテープの状態

うーんこれだけだとよくわからんということでチューリングマシンの原論文(Turing, A.M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem")を読んだけどさらに意味わからなくなった。論文名でググったらどうも日本語の解説書籍があるらしいので買って読んでます。