泰格系統

泰格系統

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

基本介紹

  • 中文名:泰格系統
  • 外文名:Tag system
  • 所屬學科:數學
這種系統以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出發的產生過程是否會進行無窮循環.此問題至今尚未解決.

相關詞條

熱門詞條

聯絡我們