標記系統

標記系統是 Emil Leon Post 在1943年創立的確定性計算模型，作為一種簡單形式的字符串重寫系統。標記系統也可以看作抽象機，叫做 Post 標記機（不要混淆於Post-圖靈機）——簡單的說，其唯一的磁帶是無限長度的FIFO 隊列的有限狀態自動機，在每次狀態轉變中機器讀在隊列頭部的符號，從頭部刪除固定數目的符號，並可以向尾部增加符號。

定義[編輯]

標記系統是三元組 (m, A, P)，這裏的

m 是正數，叫做刪除數。
A 是有限的符號字母表，其中一個是特殊的停機符號。在 A 上的有限的（可能空）字符串叫做字。
P 是產生規則的集合，指派一個字 P(x)（叫做產品）到A 中的每個符號 x。指派給停機符號的產品（就是 P(H)）在下面會看到在計算中沒有扮演任何角色，但是出於方便採用 P(H) = 'H'。

術語m-標記系統經常用來強調刪除數。定義在文獻 [1][2][3][4] 有着不同，上面的定義（來自[4]）可能最適合作為計算模型：

停機字是要麼開始於停機符號要麼長度小於 m 的字。
變換 t 定義在非停機字上，使得如果 x 指示一個字 S 的最左符號，則 t(S) 是刪除 S 的最左的 m 符號並添加字 P(x) 到右邊。
標記系統做的計算是重複變換 t 所產生的字的有限序列，開始於初始給定的字並在產生停機字的時候停機。（計算不被認為要退出，除非在有限多重複中生成停機字。）

對於每個 m > 1，m-標記系統的集合是圖靈完全的。特別是，Rogozhin [4] 建立了 2-標記系統普遍性的類，使用字母表 {a₁, ..., a_n, H} 和相應的產品 {a_na_nW₁, ..., a_na_nW_n-1, a_na_n, H}，這裏的 W_k 是非空字。

注意不像標記系統的某些可替代的定義那樣，當前的定義中一個計算的「輸出」可以編碼在最終的字中。

例子[編輯]

2-标记系统
    字母表: {a,b,c,H} 
    产生规则:
         a  -->  ccbaH
         b  -->  cca
         c  -->  cc

计算
    初始字: baa
             acca
               caccbaH
                 ccbaHcc
                   baHcccc
                     Hcccccca (停机)。

引用[編輯]

[1] Wang, H.："Tag Systems and Lag Systems", Math. Annalen 152, 65-74, 1963.
[2] Cocke, J.，and Minsky，M.: "Universality of Tag Systems with P=2", J. Assoc. Comput. Mach. 11, 15-20, 1964.
[3] Uspensky, V.A.: "A Post Machine" (in Russian), Moscow, "Nauka", 1979.
[4] Rogozhin, Yu.: "Small Universal Turing Machines", Theoret. Comput. Sci. 168, 215-240, 1996.

外部連結[編輯]

http://mathworld.wolfram.com/TagSystem.html （頁面存檔備份，存於互聯網檔案館）
http://mathworld.wolfram.com/CyclicTagSystem.html （頁面存檔備份，存於互聯網檔案館）
http://www.wolframscience.com/nksonline/page-95 （頁面存檔備份，存於互聯網檔案館） (cyclic tag systems)
http://www.wolframscience.com/nksonline/page-669 （頁面存檔備份，存於互聯網檔案館） (emulation of tag systems)
C++ Simulator of a Nondeterministic and Deterministic Multitape Post Machine (free software).
Bitwise Cyclic Tag (a bitwise variant of cyclic tag systems)