泰格系統

泰格系統(Tag system)一種特殊的波斯特正規系統.它是由波斯特(Post , E. L.)於20世紀20年代首先研究的.

這種系統以{0,1}為字母表，其產生式都是形如a;->}3的一元產生式，並且同一個泰格系統中所有產生式之前提都具有相同的長度.不僅如此，其產生式被前提中的第一個字母所確定，即當兩個產生式a,-月‘和a}->風中前a;,a，的第一個字母相同時，必有a;=a}和}j} _風.閡斯基(Min-sky,M. L.)於1961年證明了任何遞歸函式都可用某個泰格系統來計算.這種限制極強的系統與圖靈機有相同的計算能力.1921年，波斯特提出了一個與泰格系統相關的問題:設泰格系統T的產生式為Oabx->x00和labx->x1101，其中a,bE {0,1}，二為變數，則對QE X0,1}"，在T中從Q出發的產生過程是否會進行無窮循環.此問題至今尚未解決.