标记系统

标记系统是 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  -->  ccbaH
         b  -->  cca
         c  -->  cc

计算
    初始字: baa
             acca
               caccbaH
                 ccbaHcc
                   baHcccc
                     Hcccccca (停机)。

引用

  • [1] Wang, H.："Tag Systems and Lag Systems", Math. Annalen 152, 65-74, 1963.
  • [2] Cocke, J.，and Minsky，M.: "Universality of Tag Systems with P=2", J. Assoc. Comput. Mach. 11, 15-20, 1964.
  • [3] Uspensky, V.A.: "A Post Machine" (in Russian), Moscow, "Nauka", 1979.
  • [4] Rogozhin, Yu.: "Small Universal Turing Machines", Theoret. Comput. Sci. 168, 215-240, 1996.

外部链接