タグシステム

計算理論において、タグシステムとは、1943年にエミール・レオン・ポストがポスト正準システムの単純な形式として発表した計算の決定論的モデルである。^{[1]タグシステムは、ポストタグマシン（}ポストチューリングマシンと混同しないように）と呼ばれる抽象マシンとみなすこともできる。簡単に言えば、ポストタグマシンは、長さが無制限のFIFO キューのみをテープとする有限状態マシンであり、各遷移においてマシンはキューの先頭にあるシンボルを読み取り、先頭から定数個のシンボルを削除し、この遷移で読み取られた最初のシンボルにのみ依存するシンボル文字列を末尾に追加する。

指定されたすべての操作は単一の遷移で実行されるため、タグマシンには厳密に 1 つの状態しかありません。

定義

タグシステムは（ m、A、P ）の3つ組であり、

m は正の整数で、削除数と呼ばれます。
A は有限の記号アルファベットであり、そのうちの 1 つは特別な停止記号である可能性があります。A上のすべての有限の (空の可能性がある) 文字列は単語と呼ばれます。
P は生成規則の集合であり、 A内の各シンボルxに単語P(x) (生成規則と呼ばれる) を割り当てます。停止シンボルに割り当てられた生成規則 ( P( H )とする) は、以下では計算では役割を果たさないように見えますが、便宜上P( H ) = 'H'とします。

停止語とは、停止記号で始まるか、長さがm未満の単語です。

変換t (タグ操作と呼ばれる) は、非停止単語の集合に対して定義されます。つまり、x が単語Sの左端の記号を表す場合、t ( S ) は、 Sの左端のm個の記号を削除し、右側に単語P(x)を追加した結果になります。したがって、システムは m 個の記号のヘッドを可変長のテールに処理しますが、生成されるテールはヘッドの最初の記号のみに依存します。

タグシステムによる計算は、最初に与えられた単語から開始し、停止単語が生成されると停止する変換 t を反復することによって生成される有限の単語シーケンスです。(この定義では、有限回の反復で停止単語が生成されない限り、計算は存在するとは見なされません。別の定義では、出力をエンコードする単語を識別するためにアルファベットの特別なサブセットを使用するなど、停止しない計算が許可されます。)

mタグシステムという用語は、欠失数を強調するためによく使用されます。定義は文献によって多少異なりますが（参考文献を参照）、ここで紹介するのはRogozhinの定義です。^[2]

上記の定義で停止記号を使用すると、計算の出力を最後の単語のみにエンコードできますが、そうでない場合は、出力はタグ操作を反復して生成される単語のシーケンス全体にエンコードされます。

一般的な代替定義では、停止記号を使用せず、長さがm未満のすべての単語を停止単語として扱います。別の定義は、Post (1943) によって使用された元の定義 (以下の歴史的注記で説明) であり、停止単語は空の文字列のみです。

例: シンプルな2タグのイラスト

これは、停止記号を使用する単純な 2 タグシステムを説明するだけです。

2タグシステム
    アルファベット: {a,b,c,H}
    制作ルール:
         a --> ccbaH
         b --> 約
         c --> cc

計算
    最初の単語: baa
                    アッカ
                      カッチャH
                        ccbaHcc
                          バハック
                            Hccccccca（止まれ）。

例: コラッツ列の計算

この単純な 2 タグシステムは、De Mol (2008) から採用したものです。停止記号は使用しませんが、長さが 2 未満の単語で停止し、Collatz シーケンスのわずかに修正されたバージョンを計算します。

元のコラッツ数列では、nの次の数列は⁠ん/2⁠ (偶数 nの場合) または 3 n + 1 (奇数 n の場合)。3 n + 1 の値は奇数n の場合に明らかに偶数なので、 3 n + 1の次の項は確実に⁠3n +1です/2⁠。以下のタグシステムによって計算されるシーケンスでは、この中間ステップをスキップするため、nの後続は⁠になります。3n +1です/2⁠ nが奇数の場合。

このタグシステムでは、正の整数n はn個の aを含む単語 aa...a で表されます。

2タグシステム
    アルファベット: {a,b,c}
    制作ルール:
         a --> bc
         b --> a
         c --> ああ

計算
    最初の単語: aaa <--> n=3
                    アブ  
                      シービーシー
                        きゃあ
                          ああああ <--> 5
                            ああ
                              アブ
                                bcbc
                                  cbcaaa
                                    きゃあああ
                                      ああああああ <--> 8
                                        ああああああ
                                          ああああ
                                            ああ、ああ
                                              bcbcbcbc
                                                bcbcbca
                                                  ばくばく
                                                    ばあ
                                                      ああ <--> 4
                                                        ABC
                                                          bcbc
                                                            bca
                                                              ああ <--> 2
                                                                紀元前
                                                                  1 <--> 1
                                                                   （停止）

チューリング完全性メートル-タグシステム

各m > 1 について、 mタグシステムの集合はチューリング完全である。つまり、各m > 1 について、任意のチューリングマシン Tに対して、 T をエミュレートするmタグシステムが存在する。特に、 Wang (1963) や Cocke & Minsky (1964) によって行われたように、ユニバーサルチューリングマシンをエミュレートする 2 タグシステムを構築することができる。

逆に、チューリングマシンは、チューリング完全なクラスのmタグシステムをエミュレートできることを証明することで、ユニバーサルチューリングマシンであることを示すことができます。たとえば、Rogozhin (1996) は、アルファベット { a ₁、...、a _n、H } と対応する生成規則 { a _n a _n W ₁、...、a _n a _n W _n-1、a _n a _n、H } を使用して、2 タグシステムのクラスのユニバーサル性を証明しました。ここで、W _{k は}空でない単語です。次に、非常に小さな (4 状態、6 シンボル) チューリングマシンが、このクラスのタグシステムをシミュレートできることを示して、そのユニバーサル性を証明しました。

2タグシステムは、時間内での汎用チューリングマシンの効率的なシミュレータです。つまり、が時間で実行される決定論的なシングルテープチューリングマシンである場合、それを時間でシミュレートする2タグシステムがあります。^[3] $O(t^{4}\ln^{2}t)$ $M$ $t$ $O(t^{4}\ln^{2}t)$

2タグ停止問題

このバージョンの停止問題は、最も単純で、最も簡単に記述できる決定不可能な決定問題の 1 つです。

任意の正の整数nとアルファベット {1,2,..., n } 上のn + 1 個の任意の単語P ₁、P ₂、...、P _n、Qのリストが与えられた場合、タグ操作t : ijX → XP _iを繰り返し適用すると、最終的にQ は長さが 2 未満の単語に変換されますか? つまり、シーケンスQ、t ¹ ( Q )、t ² ( Q )、t ³ ( Q )、... は終了しますか?

タグシステムの定義に関する歴史的メモ

上記の定義はPost (1943)の定義とは異なります。Postのタグシステムは停止記号を使用せず、空の単語でのみ停止し、タグ操作tは次のように定義されます。

x が空でない単語Sの左端の記号を表す場合、t ( S ) は、最初に単語P(x) をSの右端に追加し、次に結果の左端のm個の記号を削除する操作です。記号がm個未満の場合はすべてを削除します。

m > 1の場合のmタグシステムのセットのチューリング完全性に関する上記のコメントは、Post によって最初に定義されたこれらのタグシステムにも適用されます。

「タグ」という名前の由来

ポスト (1943) の脚注によると、BP ギルは、最初のm個のシンボルはそのまま残し、現在の位置を示すチェックマークが各ステップごとにm個のシンボルずつ右に移動する、という問題の初期の変種に名前を提案しました。チェックマークがシーケンスの末尾に触れるかどうかを判断する問題は、子供の鬼ごっこにちなんで「鬼ごっこの問題」と呼ばれました。

循環タグシステム

循環タグシステムは、元のタグシステムを修正したものです。アルファベットは0と1 の2 つの記号のみで構成され、生成規則は、リストの「最後の」生成を検討した後、リストの先頭に戻る、順番に検討される生成のリストで構成されます。各生成について、単語の左端の記号が調べられます。記号が1の場合、現在の生成が単語の右端に追加されます。記号が0の場合、単語に文字は追加されません。どちらの場合も、左端の記号は削除されます。単語が空になると、システムは停止します。^[4]

例

循環タグシステム
 作品数: (010, 000, 1111)

計算
 最初の単語: 11001
    制作ワード
    ---------- --------------
       010 11001
       000 1001010
       1111 001010000
       010 01010000
       000 1010000
       1111 010000000
       010 10000000
        . .
        . .

巡回タグシステムはマシュー・クックによって作成され、ルール110セルオートマトンが普遍的であるというクックのデモンストレーションで使用されました。 ^{[5]デモンストレーションの重要な部分は、巡回タグシステムが}チューリング完全なクラスのタグシステムをエミュレートできることでした。

巡回タグシステムによるタグシステムのエミュレーション

アルファベット{ a ₁ , ..., a _n } と対応する生成規則 { P ₁ , ..., P _n } を持つ m タグシステムは、 m*n 個の生成規則 ( Q 1 , ..., Q n , -, -, ..., - ) を持つ巡回タグシステムによってエミュレートされます。ここで、_最初のn_個を除くすべての生成規則は空の文字列 (' - ' で示される) です。Q _{k は}、タグシステムアルファベットの各シンボルを次のように長さn のバイナリ文字列に置き換えることによって得られる、それぞれのP _kのエンコードです (これらは、タグシステム計算の最初の単語にも適用されます)。

1 = ₁₀₀ ...00
 ₂ = 010...00
。
。
。
n = 000...01
_です

つまり、_kは、左からk^{番目の位置に}1が、その他の位置に0が入ったバイナリ文字列としてエンコードされます。タグシステム計算の連続行は、^{巡回タグシステムによるエミュレーションの (}m*n )行ごとにエンコードされます。

例

これはエミュレーション技術を説明するための非常に小さな例です。

2タグシステム
    生成規則: (a --> bb、b --> abH、H --> H)
    アルファベットのエンコード: a = 100、b = 010、H = 001
    生産エンコーディング: (bb = 010 010、abH = 100 010 001、H = 001)

循環タグシステム
    作品: (010 010、100 010 001、001、-、-、-)

タグシステムの計算
    最初の単語: ba
                    アブH
                      Hbb（停止）

循環タグシステムの計算
    最初の単語: 010 100 (=ba)

    制作ワード
    ---------- -----------------------------
  * 010 010 010 100 (=バ)
    100 010 001 10 100
    001 0 100 100 010 001
    - 100 100 010 001
    - 00 100 010 001
    - 0 100 010 001
  * 010 010 100 010 001 (=abH)
    100 010 001 00 010 001 010 010
    001 0 010 001 010 010
    - 010 001 010 010
    - 10 001 010 010
    - 0 001 010 010
  * 010 010 エミュレートされた停止 --> 001 010 010 (=Hbb)
    100 010 001 01 010 010
    001 1 010 010
    - 010 010 001
    ……

巡回タグシステムによって生成される6 行目ごとに (「*」でマークされます)、エミュレートされた停止に達するまで、タグシステム計算の対応する行がエンコードされます。

参照

注記

^ 1943年以降。
^ ロゴジン 1996年。
^ Woods, Damien; Neary, Turlough (2009-02-17). 「小型汎用チューリングマシンの複雑さ: 概観」(PDF) .理論計算機科学. 自然からの計算パラダイム. 410 (4): 443–450. doi :10.1016/j.tcs.2008.09.051. ISSN 0304-3975. S2CID 10257004.
^ ミンスキー (1967) は、第 14 章「計算可能性のための非常に単純な基底」で、非常に読みやすく (例も挙げて) 14.6 「タグ」と単一遺伝子標準システムの問題(pp. 267–273) というサブセクションを提示している (このサブセクションは「タグシステム」として索引付けされている)。ミンスキーは、一般的な問題に関する苛立たしい経験を次のように語っている。「ポストはこの (00, 1101) 問題を「手に負えない」と感じたが、私も、コンピュータの助けを借りてもそう思った」。彼は、「任意の文字列 S について、S で開始したときにこのプロセスが繰り返されるかどうかを効果的に判断する方法」は不明だが、いくつかの特定のケースは解決不可能であることが証明されているとコメントしている。特に、彼は 1964 年のコックの定理と系について言及している。
^ クック 2004年。

参考文献

コック、ジョン;ミンスキー、マービン(1964)。「P = 2のタグシステムの普遍性」。計算機協会誌。11 : 15–20。doi :10.1145/321203.321206。hdl : 1721.1 /6107。S2CID 2799125 。
Cook, Matthew (2004). 「Universality in Elementary Cellular Automata」. Complex Systems . 15 : 1–40. doi :10.25088/ComplexSystems.15.1.1. 2016年5月28日時点のオリジナルよりアーカイブ(PDF) 。
De Mol, Liesbeth (2008 年 1 月). 「タグシステムと Collatz のような関数」.理論計算機科学. 390 (1): 92–101. doi :10.1016/j.tcs.2007.10.020. hdl : 1854/LU-436211 .
ミンスキー、マーヴィン L. (1961 年11月)。「ポストの「タグ」問題の再帰的解決不可能性とチューリングマシン理論におけるその他の話題」。Annals of Mathematics。2 . 74 ( 3): 437–455。doi :10.2307/1970290。JSTOR 1970290。
ミンスキー、マーヴィン L. (1967)。『計算：有限マシンと無限マシン』。ニュージャージー州エングルウッドクリフス：プレンティス・ホール。pp. 267–273。ISBN 978-0131655638LCCN 67-12342 。
ポスト、エミール(1943)。「組み合わせ決定問題の形式的簡約」。アメリカ数学ジャーナル。65 (2) : 197–215。doi :10.2307 / 2371809。JSTOR 2371809。(タグシステムについては、203 ページ以降で紹介されています。)
Rogozhin, Yurii (1996 年 11 月 20 日). 「小型汎用チューリングマシン」.理論計算機科学. 168 (2): 215–240. doi :10.1016/S0304-3975(96)00077-1.
王昊（1963年）。「タグシステムとラグシステム」。数学アンナレン。152：65～74。土井：10.1007/BF01343730。S2CID 120383146。

外部リンク

https://mathworld.wolfram.com/TagSystem.html
https://mathworld.wolfram.com/CyclicTagSystem.html
https://www.wolframscience.com/nks/p95/ (循環タグシステム)
https://www.wolframscience.com/nks/p669/ (タグシステムのエミュレーション)

[FOOTNOTEPost1943-1] 1943年以降。

[FOOTNOTERogozhin1996-2] ロゴジン 1996年。

[3] Woods, Damien; Neary, Turlough (2009-02-17). 「小型汎用チューリングマシンの複雑さ: 概観」(PDF) .理論計算機科学. 自然からの計算パラダイム. 410 (4): 443–450. doi :10.1016/j.tcs.2008.09.051. ISSN 0304-3975. S2CID 10257004.

[4] ミンスキー (1967) は、第 14 章「計算可能性のための非常に単純な基底」で、非常に読みやすく (例も挙げて) 14.6 「タグ」と単一遺伝子標準システムの問題(pp. 267–273) というサブセクションを提示している (このサブセクションは「タグシステム」として索引付けされている)。ミンスキーは、一般的な問題に関する苛立たしい経験を次のように語っている。「ポストはこの (00, 1101) 問題を「手に負えない」と感じたが、私も、コンピュータの助けを借りてもそう思った」。彼は、「任意の文字列 S について、S で開始したときにこのプロセスが繰り返されるかどうかを効果的に判断する方法」は不明だが、いくつかの特定のケースは解決不可能であることが証明されているとコメントしている。特に、彼は 1964 年のコックの定理と系について言及している。

[FOOTNOTECook2004-5] クック 2004年。