Geekly Articles each Day

MySQL Turing Machine Emulator

最近、インタビューの1つで、MySQLツールのみを使用して文字列を解析するタスクが与えられました。
その後、私は考えました：一般に、この種の複雑なタスクは、1つのDBMSだけでどのように解決できるのでしょうか？ 答えはすぐに見つかりました。MySQLツールを使用すると、文字列認識タスク全般を解決できます。 そして、これをより便利で普遍的な方法で行うには、原始的な有限状態マシンエミュレーター、さらに良いことに、Turingマシンを作成するだけで十分です。もちろん、MySQLが提供するコンストラクトのみを使用します。 それでは、実験を始めましょう。

設計中

すべてのプログラムはプロジェクトから始まります。 それで、今回がそうです。 まず第一に、チューリングマシンとは何ですか、それは何をしますか、何ができますか？ 彼女は率直に言って少し知っています。 エンドレスベルトと制御装置（キャリッジ）を自由に使用できるため、マシンは次のことができます。
  1. テープに沿って左右に移動する
  2. テープ記号から読み取ります。
  3. テープに書き込む記号
  4. さまざまな州に行く

ロシア語に翻訳されたチューリング機械の指示は、次のように聞こえます。
もちろん、この方法でチューリングマシンに指示を与えることはあまり便利ではないため、次のように指示を形式化します。
'>'-右に移動
'<'-左に移動
「＃」-停止
マシンの一連の指示の例を次に示します。
0、1、>、1
1,0、>、2
2.0、>、3
3 ,,>、4
4、1、4
4,1、＃、4

このかなり役に立たないプログラムは、テープに書き込まれた2進数が4であるかどうかをチェックし、4である場合は、スペースを介して1を書き込みます。
このマシンはいくつかの仮定を暗示しています。
第一に、制御デバイスの初期位置は、元のデータの右側ではなく左側にある場合があります。
第二に、テープは一方向にのみ「無限」です。
第三に、ご覧のとおり、文字を読み取った後の上記のチューリングマシンは、文字を書き込むかテープに沿って移動するという1つのことしかできません。 これらの仮定に基づいてエミュレータを設計します。

プロジェクト全体は、次の部分で構成されます。

  1. 単一のフィールドで構成されるテープをシミュレートするために設計されたテーブル
  2. エラー出力テーブル、1つのフィールドも
  3. 4つのフィールド（初期状態、読み取るシンボル、アクション、結果の状態）からの命令自体のテーブル。
  4. エミュレータロジックを含むストアドプロシージャ。


エラー出力テーブルは何のためですか？ まあ、それはまだある種ですが、最も原始的な言語のインタプリタです。 したがって、プログラムがつまずいた理由に関する情報は不要ではありません。
それでは、エミュレータはどのように機能しますか？ ルールに従って1つの命令-1行、プログラムのテキストを目的のテーブルに挿入し、ソースデータをテープテーブルに挿入して手順を開始します。 プログラムに書き込む内容によっては、最終的にテープに書き込まれます。 完全に予期しないことがある場合は、エラーテーブルを確認できます。
それでは、コーディングの部分を開始します。

開発中です

まず、データベースとテーブルを作成します。

CREATE DATABASE turing; CREATE TABLE program ( in_state INT NOT NULL , sread VARCHAR( 1 ) NOT NULL , actions VARCHAR( 1 ) NOT NULL , out_state INT NOT NULL ) ENGINE = MYISAM CHARACTER SET utf8 COLLATE utf8_unicode_ci; CREATE TABLE output_string ( output TEXT NOT NULL ) ENGINE = MYISAM ; CREATE TABLE ribbon ( sinput TEXT NOT NULL ) ENGINE = MYISAM ;


output_stringエラーを出力するためのテーブルでは、空の行を1つ作成し、それ以上触れないようにする必要があります。

次に、最も重要なこと-プロシージャの作成に進みます。 しかしその前に、MySQL configで再帰を有効にする必要があります。それは非常に必要だからです。
これを行うには、my.cnfにmax_sp_recursion_depth = 255と記述します。

最初に、コメントでビューを損なわないように、手順コードを完全に提供し、以下で復号化を提供します。

 delimiter // CREATE procedure turing(IN sstate INT(11), IN pos INT(11)) BEGIN turing:BEGIN SET @p=pos; SET @sstate=sstate; SELECT @inread:=SUBSTRING(sinput, @p, 1) FROM ribbon; SELECT @instate:=in_state, @sread:=sread, @actions:=actions, @out_state:=out_state, @numrows:=count(in_state) FROM program WHERE in_state = @sstate AND sread = @inread; IF @numrows > 1 THEN UPDATE output_string SET output= 'Confused :('; LEAVE turing; ELSEIF @numrows = 0 THEN UPDATE output_string SET output='Do not understand what to do next :('; LEAVE turing; ELSE SELECT @lin:= LENGTH(sinput) FROM ribbon; SELECT @input:=sinput FROM ribbon; IF @actions = '>' THEN IF @lin = pos THEN SELECT @new_input:=CONCAT(sinput, ' ') FROM ribbon; UPDATE ribbon SET sinput=@new_input; END IF; SET @pos=pos+1; ELSEIF @actions = '<' THEN IF pos>1 THEN SET @pos=pos-1; ELSE UPDATE output_string SET output='Carriage has left the ribbon'; LEAVE turing; END IF; ELSEIF @actions = '#' THEN LEAVE turing; ELSE SELECT @head:=SUBSTRING(sinput, 1, pos-1) FROM ribbon; SELECT @tail:=SUBSTRING(sinput, pos+1, @lin) FROM ribbon; SELECT @inp:=CONCAT(@head, @actions, @tail); UPDATE ribbon SET sinput=@inp; SET @pos=pos; END IF; CALL turing(@out_state, @pos); END IF; END; END //

始まりは明らかです。プロシージャを作成し、2つのパラメータを渡します-ステートマシンの状態と制御デバイスposの位置。

次に、BEGIN ... ENDブロックにチューリングラベルを付けて、終了に使用できるようにします。

その後、キャリッジが現在配置されているシンボルを@inread変数に読み込みます。

プログラムテーブルから、渡されたパラメーターと状態が等しい行、および読み取りフィールド-読み取られる文字は、制御デバイスが配置されている実際の文字と等しい行を選択します。 これら2つのパラメーターは、チューリングマシンの命令を一意に決定するため、条件を満たすラインは一意である必要があります。

対応する指示がない状況を処理します-エミュレーターはエラーを出して作業を終了します-彼は次に何をすべきかわかりません。

条件を満たす複数の命令が存在する状況を処理します。 この場合、マシンは次に何をすべきかもわからず、エミュレータはエラーで終了し、混乱していることを示します。

すべてが正常な場合、つまり行数が1の場合、入力行の長さを考慮してアクションの処理を開始します。 まず、テープは一方向に無限でなければならず、入力データの長さは決して無限ではないことを覚えておく必要があります。 したがって、制御デバイスが入力行の最後にあり、プログラムが右側への移動を指示する場合、スペースをいくつか追加して命令を実行し、位置を1増やします。

左への移動の場合、キャリッジがテープの制限を超える状況を処理します。 何もする必要はありません。 申し訳ありませんが、テープは一方向にのみ「無限」です。

プログラムが＃記号で示される「停止」信号を送信すると、手順を終了します。

シンボルが上記のいずれにも一致しない場合、つまり、>、<、または＃ではない場合、これはテープに書き込む必要があり、現在のテープを上書きする必要があることを意味します。 このトリックは、単純な組み込み関数CONCAT（）を使用して行います。

さらに、同じ精神で、既に変更されたパラメーター値を渡し続けます。 この場合の@out_stateは出力状態であり、次の命令の入力です。

テスト中

それで、私たちは最終段階に来ます-テスト。 MySQLが実際に全能であることを証明するために、このエミュレータで重要なことをしたかったのです。 したがって、ローマ数字を検証するために、かなり一般的ではあるがかなり重要な問題を解決します。
プログラムは非常に単純に動作します-文字列を入力として受け入れ、この文字列が正しいローマ数字である場合、スペースバー「Ok」にスペースを印刷します。
明らかな複雑さにもかかわらず、タスクは簡単です。 ローマ数字を書くために使用される各文字は、それに続くことができないものを決定するために必要です。 たとえば、Lの後にCを付けることはできません。つまり、エントリLCをローマ数字と見なすことはできません。 数字の50は、単純にLと表記されます。または、たとえば、連続するIの最大数は3です。したがって、IIIIはローマ数字などではありません。 これは別の記事のトピックであるため、これらの規則については詳しく説明しません。
入力アルファベットは次の文字で構成されています：M、D、C、L、X、V、およびI 、0から開始する必要はありません（少なくともこのエミュレーターでは、ゼロ状態はまったく必要ありません）。
プログラムをデータベースに挿入します。

プログラム値に挿入する
（47、 ''、 '＃'、47）、（48、 ''、 '>'、64）、（49、 ''、 '>'、64）、
（50、 ''、 '>'、64）、（51、 ''、 '>'、64）、（52、 ''、 '>'、64）、
（53、 ''、 '>'、64）、（54、 ''、 '>'、64）、（55、 ''、 '>'、64）、
（56、 ''、 '>'、64）、（57、 ''、 '>'、64）、（58、 ''、 '>'、64）、
（59、 ''、 '>'、64）、（60、 ''、 '>'、64）、（61、 ''、 '>'、64）、
（62、 ''、 '>'、64）、（63、 ''、 '>'、64）、（65、 ''、 '>'、64）、
（66、 ''、 '>'、64）、（64、 ''、 'O'、64）、（64、 'O'、 '>'、70）、
（70、 ''、 'k'、70）、（70、 'k'、 '>'、71）、

（47、「I」、「>」、48）、（48、「V」、「>」、51）、（48、「X」、「>」、51）、
（51、 'V'、 '＃'、51）、（51、 'C'、 '＃'、51）、（51、 'L'、 '＃'、51）、
（51、 'D'、 '＃'、51）、（51、 'M'、 '＃'、51）、（51、 'X'、 '＃'、51）、

（48、「C」、「＃」、48）、（48、「L」、「＃」、48）、（48、「D」、「＃」、48）、
（48、「M」、「＃」、48）、（48、「I」、「>」、49）、（49、「I」、「>」、50）、
（50、 'I'、 '＃'、50）、（50、 'V'、 '＃'、50）、（50、 'C'、 '＃'、50）、
（50、 'L'、 '＃'、50）、（50、 'D'、 '＃'、50）、（50、 'M'、 '＃'、50）、
（50、「X」、「＃」、50）、

（47、「V」、「>」、52）、（52、「I」、「>」、48）、（52、「V」、「＃」、48）、
（52、「X」、「＃」、48）、（52、「C」、「＃」、48）、（52、「M」、「＃」、48）、
（52、「D」、「＃」、48）、（52、「L」、「＃」、48）、（47、「X」、「>」、53）、
（53、「V」、「>」、52）、（53、「I」、「>」、48）、（53、「D」、「＃」、53）、

（53、 'M'、 '＃'、53）、（53、 'L'、 '>'、53）、（53、 'C'、 '>'、53）、
（53、「X」、「>」、55）、（55、「D」、「＃」、55）、（55、「M」、「＃」、55）、
（55、 'C'、 '＃'、55）、（55、 'L'、 '＃'、55）、（55、 'V'、 '>'、52）、
（55、「I」、「>」、48）、（55、「X」、「>」、56）、（56、「X」、「＃」、56）、
（56、 'D'、 '＃'、56）、（61、 'C'、 '>'、62）、（56、 'M'、 '＃'、56）、
（56、 'C'、 '＃'、56）、（56、 'L'、 '＃'、56）、（56、 'V'、 '>'、52）、
（56、「I」、「>」、48）、

（47、 'L'、 '>'、54）、（54、 'X'、 '>'、53）、（54、 'V'、 '>'、52）、
（54、「I」、「>」、48）、（54、「D」、「＃」、54）、（54、「C」、「＃」、54）、
（54、「M」、「＃」、54）、（54、「L」、「＃」、54）、

（47、 'C'、 '>'、59）、（59、 'X'、 '>'、53）、（59、 'I'、 '>'、48）、
（59、 'L'、 '>'、54）、（59、 'V'、 '>'、52）、（59、 'M'、 '>'、65）、
（65、「M」、「＃」、65）、（65、「V」、「>」、59）、（65、「X」、「>」、59）、
（65、 'I'、 '>'、59）、（65、 'L'、 '>'、59）、（65、 'C'、 '＃'、65）、

（59、 'D'、 '>'、66）、（66、 'D'、 '＃'、66）、（66、 'M'、 '＃'、65）、
（66、 'V'、 '>'、59）、（66、 'X'、 '>'、59）、（66、 'I'、 '>'、59）、
（66、 'L'、 '>'、59）、（66、 'C'、 '＃'、65）、（59、 'C'、 '>'、61）、
（61、 'C'、 '>'、62）、（61、 'I'、 '>'、47）、（62、 'X'、 '>'、53）、
（62、「I」、「>」、48）、（62、「L」、「>」、54）、（62、「V」、「>」、52）、
（62、 'C'、 '＃'、62）、（61、 'M'、 '＃'、59）、（61、 'D'、 '＃'、59）、
（62、「M」、「＃」、62）、（62、「D」、「＃」、62）、

（47、 'D'、 '>'、60）、（60、 'M'、 '＃'、60）、（60、 'C'、 '>'、59）、
（60、 'D'、 '＃'、60）、（60、 'X'、 '>'、53）、（60、 'I'、 '>'、48）、
（60、「L」、「>」、54）、（60、「V」、「>」、52）、

（47、 'M'、 '>'、63）、（63、 'M'、 '>'、63）、（63、 'C'、 '>'、59）、
（63、 'D'、 '>'、60）、（63、 'X'、 '>'、53）、（63、 'I'、 '>'、48）、
（63、「V」、「>」、52）、（63、「L」、「>」、54）

プログラムの最初のブロックは最終段階を担当します-数値が検証に合格し、キャリッジがスペースに到達すると、ここに到達します。 この瞬間から、「OK」と入力し始めます。

次のブロックは、機械条件と入力アルファベットの文字のさまざまな組み合わせからの命令です。 ほとんどのコードは何度も使用されます。 たとえば、シンボルIのすべてのルールを作成し、シンボルVに書き込むと、（47、 'V'、 '>'、52）、（52、 'I'、 '>'、48）、ここで、状態48はすでに以前に説明されています。

そして、結果は何ですか？ 入力行として、たとえばCCCXXIV（正しい番号）として挿入します。 次に、コンソールに入力します。

mysql> call turing（47,1）//

47-初期状態、1-制御デバイスの位置。

取得するもの：

+ -------------------------------------- +

| CCCXXIV OK |

+ -------------------------------------- +

MXXLCのように、間違った番号を試してください。
取得するもの：

+ ---------------- +

| MXXLC |

+ ---------------- +

それだけです！

まとめると

エミュレータのこの実施形態は理想的ではなく、無限に洗練され改善される可能性があります。 これは単なるプロトタイプであり、MySQLを使用する明白な可能性とはほど遠いものです。 もちろん、この実装は、スポーツへの関心と楽しい娯楽のためだけに作成されました。 この記事を読んで楽しんでもらえたら幸いです。

たくさんのクレイジーなアイデアと優れたプログラミングを手に入れましょう！

Source: https://habr.com/ru/post/J109611/

More articles:


All Articles