[科普中國]-標(biāo)記系統(tǒng)

標(biāo)記系統(tǒng)是 Emil Leon Post 在1943年創(chuàng)立的確定性計(jì)算模型，作為一種簡單形式的字符串重寫系統(tǒng)。

簡介標(biāo)記系統(tǒng)也可以看作抽象機(jī)，叫做Post 標(biāo)記機(jī)（不要混淆于Post-圖靈機(jī)）——簡單的說，其唯一的磁帶是無限長度的FIFO隊(duì)列的有限狀態(tài)自動(dòng)機(jī)，在每次狀態(tài)轉(zhuǎn)變中機(jī)器讀在隊(duì)列頭部的符號(hào)，從頭部刪除固定數(shù)目的符號(hào)，并可以向尾部增加符號(hào)。1

定義標(biāo)記系統(tǒng)是三元組 (m,A,P)，這里的

m是正數(shù)，叫做刪除數(shù)。

A是有限的符號(hào)字母表，其中一個(gè)是特殊的停機(jī)符號(hào)。在A上的有限的（可能空）字符串叫做字。

P是產(chǎn)生規(guī)則的集合，指派一個(gè)字P(x)（叫做產(chǎn)品）到A中的每個(gè)符號(hào)x。指派給停機(jī)符號(hào)的產(chǎn)品（就是P(H)）在下面會(huì)看到在計(jì)算中沒有扮演任何角色，但是出于方便采用P(H)='H'。

術(shù)語m-標(biāo)記系統(tǒng)經(jīng)常用來強(qiáng)調(diào)刪除數(shù)。定義在文獻(xiàn) [1][2][3][4] 有著不同，上面的定義（來自[4]）可能最適合作為計(jì)算模型：

停機(jī)字是要么開始于停機(jī)符號(hào)要么長度小于m的字。

變換t定義在非停機(jī)字上，使得如果x指示一個(gè)字S的最左符號(hào)，則t(S) 是刪除S的最左的m符號(hào)并添加字P(x)到右邊。

標(biāo)記系統(tǒng)做的計(jì)算是重復(fù)變換t所產(chǎn)生的字的有限序列，開始于初始給定的字并在產(chǎn)生停機(jī)字的時(shí)候停機(jī)。（計(jì)算不被認(rèn)為要退出，除非在有限多重復(fù)中生成停機(jī)字。）

對(duì)于每個(gè)m> 1，m-標(biāo)記系統(tǒng)的集合是圖靈完全的。特別是，Rogozhin [4] 建立了 2-標(biāo)記系統(tǒng)普遍性的類，使用字母表 {a1, ...,an,H} 和相應(yīng)的產(chǎn)品 {ananW1, ...,ananWn-1,anan,H}，這里的Wk是非空字。

注意不像標(biāo)記系統(tǒng)的某些可替代的定義那樣，當(dāng)前的定義中一個(gè)計(jì)算的“輸出”可以編碼在最終的字中2。

例子2-標(biāo)記系統(tǒng)

字母表: {a,b,c,H}

產(chǎn)生規(guī)則: a --> ccbaH b --> cca c --> cc

計(jì)算

初始字: baa

acca

caccbaH

ccbaHcc

baHcccc

Hcccccca (停機(jī))。

本詞條內(nèi)容貢獻(xiàn)者為:

李航 - 副教授 - 西南大學(xué)