標記系統是 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-標記系統普遍性的類，使用字母表 {a1, ...,an,H} 和相應的產品 {ananW1, ...,ananWn-1,anan,H}，這裡的Wk是非空字。
注意不像標記系統的某些可替代的定義那樣，當前的定義中一個計算的“輸出”可以編碼在最終的字中。
例子
2-標記系統
字母表: {a,b,c,H}
產生規則:a --> ccbaHb --> ccac --> cc
計算
初始字: baa
acca
caccbaH
ccbaHcc
baHcccc
Hcccccca (停機)。
