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を䜿甚する明癜な可胜性ずはほど遠いものです。 もちろん、この実装は、スポヌツぞの関心ず楜しい嚯楜のためだけに䜜成されたした。 この蚘事を読んで楜しんでもらえたら幞いです。



たくさんのクレむゞヌなアむデアず優れたプログラミングを手に入れたしょう



All Articles