版权归原作者所有,如有侵权,请联系我们

[科普中国]-标记系统

科学百科
原创
科学百科为用户提供权威科普内容,打造知识科普阵地
收藏

标记系统是 Emil Leon Post 在1943年创立的确定性计算模型,作为一种简单形式的字符串重写系统。

简介标记系统也可以看作抽象机,叫做Post 标记机(不要混淆于Post-图灵机)——简单的说,其唯一的磁带是无限长度的FIFO队列的有限状态自动机,在每次状态转变中机器读在队列头部的符号,从头部删除固定数目的符号,并可以向尾部增加符号。1

定义标记系统是三元组 (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。

例子2-标记系统

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

产生规则: a --> ccbaH b --> cca c --> cc

计算

初始字: baa

acca

caccbaH

ccbaHcc

baHcccc

Hcccccca (停机)。

本词条内容贡献者为:

李航 - 副教授 - 西南大学