標(biāo)記系統(tǒng)是 Emil Leon Post 在1943年創(chuàng)立的確定性計算模型，作為一種簡單形式的字符串重寫系統(tǒng)。
簡介
標(biāo)記系統(tǒng)也可以看作抽象機(jī)，叫做Post 標(biāo)記機(jī)（不要混淆于Post-圖靈機(jī)）——簡單的說，其唯一的磁帶是無限長度的FIFO隊列的有限狀態(tài)自動機(jī)，在每次狀態(tài)轉(zhuǎn)變中機(jī)器讀在隊列頭部的符號，從頭部刪除固定數(shù)目的符號，并可以向尾部增加符號。
定義
標(biāo)記系統(tǒng)是三元組 (m,A,P)，這里的
??m是正數(shù)，叫做刪除數(shù)。
??A是有限的符號字母表，其中一個是特殊的停機(jī)符號。在A上的有限的（可能空）字符串叫做字。
??P是產(chǎn)生規(guī)則的集合，指派一個字P(x)（叫做產(chǎn)品）到A中的每個符號x。指派給停機(jī)符號的產(chǎn)品（就是P(H)）在下面會看到在計算中沒有扮演任何角色，但是出于方便采用P(H)='H'。
術(shù)語m-標(biāo)記系統(tǒng)經(jīng)常用來強(qiáng)調(diào)刪除數(shù)。定義在文獻(xiàn) 有著不同，上面的定義（來自）可能最適合作為計算模型：
??停機(jī)字是要么開始于停機(jī)符號要么長度小于m的字。
??變換t定義在非停機(jī)字上，使得如果x指示一個字S的最左符號，則t(S) 是刪除S的最左的m符號并添加字P(x)到右邊。
??標(biāo)記系統(tǒng)做的計算是重復(fù)變換t所產(chǎn)生的字的有限序列，開始于初始給定的字并在產(chǎn)生停機(jī)字的時候停機(jī)。（計算不被認(rèn)為要退出，除非在有限多重復(fù)中生成停機(jī)字。）
對于每個m> 1，m-標(biāo)記系統(tǒng)的集合是艾倫·麥席森·圖靈完全的。特別是，Rogozhin 建立了 2-標(biāo)記系統(tǒng)普遍性的類，使用字母表 {a, ...,a,H} 和相應(yīng)的產(chǎn)品 {aaW, ...,aaW,aa,H}，這里的W是非空字。
注意不像標(biāo)記系統(tǒng)的某些可替代的定義那樣，當(dāng)前的定義中一個計算的“輸出”可以編碼在最終的字中。
例子
2-標(biāo)記系統(tǒng)
字母表: {a,b,c,H}
產(chǎn)生規(guī)則: a --> ccbaH b --> cca c --> cc
計算
初始字: baa
acca
caccbaH
ccbaHcc
baHcccc
Hcccccca (停機(jī))。
參考資料 >