1,970
次編輯
變更
标记系统
,创建页面，内容为“{| class="wikitable" align="right" |- | style="background: #66CCFF" align= center| '''<big>标记系统</big> ''' |- |<center><img src=http://img01.baimao.com/M…”
{| class="wikitable" align="right"
|-
| style="background: #66CCFF" align= center| '''<big>标记系统</big> '''
|-
|<center><img src=http://img01.baimao.com/M01/12/33/wKgAFFKBkQGAXhxLAAAoiIQO3_s962.jpg width="300"></center>
<small>[https://image.so.com/view?q=%E6%A0%87%E8%AE%B0%E6%9C%BA&src=&inact=1&correct=%E6%A0%87%E8%AE%B0%E6%9C%BA&ancestor=list&cmsid=cc6afc1e53a2ee6dac311f3a1160e98b&cmras=6&cn=0&gn=0&kn=0&crn=0&bxn=0&fsn=60&cuben=0&pornn=0&manun=0&adstar=0&clw=241#id=adb39aaec56c4c282358b2606b8db5b6&currsn=0&ps=37&pc=37 来自 360网 的图片]</small>
|-
| style="background: #66CCFF" align= center|
|-
| align= light|
|}
'''标记系统'''是 Emil Leon Post 在1943年创立的确定性计算模型，作为一种简单形式的字符串重写系统。<ref>[https://image.so.com/view?q=%E6%A0%87%E8%AE%B0%E6%9C%BA&src=&inact=1&correct=%E6%A0%87%E8%AE%B0%E6%9C%BA&ancestor=list&cmsid=cc6afc1e53a2ee6dac311f3a1160e98b&cmras=6&cn=0&gn=0&kn=0&crn=0&bxn=0&fsn=60&cuben=0&pornn=0&manun=0&adstar=0&clw=241#id=adb39aaec56c4c282358b2606b8db5b6&currsn=0&ps=37&pc=37 ],360网 , </ref>
==简介==
标记系统也可以看作[[抽象机]]，叫做Post 标记机（不要混淆于Post-图灵机）——简单的说，其唯一的[[磁带]]是无限长度的FIFO队列的有限状态自动机，在每次状态转变中机器读在队列头部的符号，从头部删除固定数目的符号，并可以向尾部增加符号。
==定义==
标记系统是三元组 (m,A,P)，这里的
m是正数，叫做删除数。
A是有限的符号字母表，其中一个是特殊的停机符号。在A上的有限的（可能空）字符串叫做字。
P是产生规则的集合，指派一个字P(x)（叫做产品）到A中的每个符号x。指派给停机符号的产品（就是P(H)）在下面会看到在计算中没有扮演任何角色，但是出于方便采用P(H)='H'。
术语m-标记系统经常用来强调删除数。定义在文献 有着不同，上面的定义（来自）可能最适合作为计算模型：
停机字是要么开始于停机符号要么长度小于m的字。
变换t定义在非停机字上，使得如果x指示一个字S的最左符号，则t(S) 是删除S的最左的m符号并添加字P(x)到右边。
标记系统做的计算是重复变换t所产生的字的有限序列，开始于初始给定的字并在产生停机字的时候停机。（计算不被认为要退出，除非在有限多重复中生成停机字。）
对于每个m> 1，m-标记系统的集合是图灵完全的。特别是，Rogozhin 建立了 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 (停机)。
== 参考来源 ==
{{reflist}}
[[Category:
400 應用科學類]]
|-
| style="background: #66CCFF" align= center| '''<big>标记系统</big> '''
|-
|<center><img src=http://img01.baimao.com/M01/12/33/wKgAFFKBkQGAXhxLAAAoiIQO3_s962.jpg width="300"></center>
<small>[https://image.so.com/view?q=%E6%A0%87%E8%AE%B0%E6%9C%BA&src=&inact=1&correct=%E6%A0%87%E8%AE%B0%E6%9C%BA&ancestor=list&cmsid=cc6afc1e53a2ee6dac311f3a1160e98b&cmras=6&cn=0&gn=0&kn=0&crn=0&bxn=0&fsn=60&cuben=0&pornn=0&manun=0&adstar=0&clw=241#id=adb39aaec56c4c282358b2606b8db5b6&currsn=0&ps=37&pc=37 来自 360网 的图片]</small>
|-
| style="background: #66CCFF" align= center|
|-
| align= light|
|}
'''标记系统'''是 Emil Leon Post 在1943年创立的确定性计算模型，作为一种简单形式的字符串重写系统。<ref>[https://image.so.com/view?q=%E6%A0%87%E8%AE%B0%E6%9C%BA&src=&inact=1&correct=%E6%A0%87%E8%AE%B0%E6%9C%BA&ancestor=list&cmsid=cc6afc1e53a2ee6dac311f3a1160e98b&cmras=6&cn=0&gn=0&kn=0&crn=0&bxn=0&fsn=60&cuben=0&pornn=0&manun=0&adstar=0&clw=241#id=adb39aaec56c4c282358b2606b8db5b6&currsn=0&ps=37&pc=37 ],360网 , </ref>
==简介==
标记系统也可以看作[[抽象机]]，叫做Post 标记机（不要混淆于Post-图灵机）——简单的说，其唯一的[[磁带]]是无限长度的FIFO队列的有限状态自动机，在每次状态转变中机器读在队列头部的符号，从头部删除固定数目的符号，并可以向尾部增加符号。
==定义==
标记系统是三元组 (m,A,P)，这里的
m是正数，叫做删除数。
A是有限的符号字母表，其中一个是特殊的停机符号。在A上的有限的（可能空）字符串叫做字。
P是产生规则的集合，指派一个字P(x)（叫做产品）到A中的每个符号x。指派给停机符号的产品（就是P(H)）在下面会看到在计算中没有扮演任何角色，但是出于方便采用P(H)='H'。
术语m-标记系统经常用来强调删除数。定义在文献 有着不同，上面的定义（来自）可能最适合作为计算模型：
停机字是要么开始于停机符号要么长度小于m的字。
变换t定义在非停机字上，使得如果x指示一个字S的最左符号，则t(S) 是删除S的最左的m符号并添加字P(x)到右边。
标记系统做的计算是重复变换t所产生的字的有限序列，开始于初始给定的字并在产生停机字的时候停机。（计算不被认为要退出，除非在有限多重复中生成停机字。）
对于每个m> 1，m-标记系统的集合是图灵完全的。特别是，Rogozhin 建立了 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 (停机)。
== 参考来源 ==
{{reflist}}
[[Category:
400 應用科學類]]