純粋なSQLチューリングマシン

数ヶ月前、私は尊敬されるksushaがMySQLとストアドプロシージャを使用してチューリングマシンエミュレータを書いた投稿を読みました。 この記事は、ストアドプロシージャを使用せずに、純粋なSQLでチューリングマシンを作成するというアイデアに弾みをつけました。 実装には、使い慣れたFirebirdバージョン2.1が使用されました。



ベアSQLでチューリングマシンを作成する場合、2つの基本的な問題があります。

• 1）マシンのテープを変更および追加できます。これには、同じデザインのINSERTおよびUPDATEステートメントが必要です。
• 2）チューリングマシンには、少なくとも1つの状態変数が必要です。 通常のSQL（DML）クエリは、少なくともFirebirdでは中間変数を保存できません。

ただし、これらの制限を回避することができました。



まず、通常のストアドプロシージャでチューリングマシンを作成しました。 ksuhaが再帰を使用した理由がわかりません。通常のループと両側の無限のリボンでそれを行いました。 そのコードには目立ったものは何もないので、すぐに裸のSQLで実装を開始しました。



Firebird 2.1の最初の問題を解決するために、MERGEとUPDATE OR INSERTの2つの構成が既にあります。

最初は2番目のレコードを使用する予定でしたが、その助けを借りて変更または挿入できるレコードは1つだけです。 MERGEを使用すると、任意の選択でテーブルを「接着」できます。



一連の実験後に状態を保存するために、バージョン2.1でも登場した再帰クエリを使用することが決定されました。



プログラムとテープを保存するために、元の投稿に似たテーブル構造が使用されました。



ここに私が終わったものがあります：

MERGE INTO ribbon r USING ( WITH RECURSIVE data AS ( SELECT 0 AS state, 1 AS pos, (SELECT sinput FROM ribbon WHERE id = 1) AS val FROM RDB$DATABASE UNION ALL SELECT p.out_state AS STATE, CASE WHEN p.actions = '<' THEN data.pos - 1 WHEN p.actions = '>' THEN data.pos + 1 ELSE data.pos END AS pos, CASE WHEN p.actions = '<' THEN COALESCE((SELECT sinput FROM ribbon WHERE id = (data.pos - 1)), ' ') WHEN p.actions = '>' THEN COALESCE((SELECT sinput FROM ribbon WHERE id = (data.pos + 1)), ' ') ELSE p.actions END AS val FROM program p JOIN data ON data.state = p.in_state WHERE p.sread = COALESCE((SELECT sinput FROM ribbon WHERE id = data.pos), ' ') AND p.actions != '#' ) SELECT * FROM data ) data ON data.pos = r.id WHEN MATCHED THEN UPDATE SET sinput = data.val WHEN NOT MATCHED THEN INSERT (id, sinput) VALUES (data.pos, data.val)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

計算された状態フィールドに状態を保存します。posはテープ上の位置です。

「FROM RDB $ DATABASE」コンストラクトは、Firebirdの「機能」であり、テーブルなしで単一行の選択を作成する必要がある場合に使用されます。

したがって、Firebird 2.1実装のDML SQLはチューリング完全なプログラミング言語と見なすことができます。 理論的には、このようなクエリは、構文の違いを考慮して、再帰クエリとMERGEなどの構造をサポートするDBMSで実行できます。

代わりに、エピローグの

最初は、状態をジェネレーター、別名SEQUENCEに保存することが計画されていました。 しかし、私はそのような要求を書くことができませんでした-テープの新しいデータのソースであり、プログラムとテープを前後に実行することができます。 それにもかかわらず、この実験により、発電機を操作する際にいくつかの興味深い解決策を見つけることができました。

• 1）WHEREセクションでジェネレーターを移動するには、デザインを使用できます
  
  

   GEN_ID(POS, <increment>)=GEN_ID(POS, 0)
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  増分値については、trueを返します。
• 2）発電機はゼロにリセットできます
  
  

   GEN_ID(POS, -GEN_ID(POS, 0))
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  1）と一緒に使用すると、WHERE句でジェネレーターをリセットできます。

Firebirdの再帰クエリのネストは1024レベルに制限されていると言わなければならないので、ジェネレーターでこれを行うことができれば、制限は解除されます。

テーブル構造

 CREATE TABLE PROGRAM ( IN_STATE INTEGER NOT NULL, SREAD CHAR(1) NOT NULL, ACTIONS CHAR(1) NOT NULL, OUT_STATE INTEGER NOT NULL ); CREATE TABLE RIBBON ( SINPUT CHAR(1) NOT NULL, ID INTEGER NOT NULL );
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ソース

Firebird 2.1リリースノート