标记系统 编辑
标记系统是 Emil Leon Post 在1943年创立的确定性计算模型，作为一种简单形式的字符串重写系统。标记系统也可以看作抽象机，叫做 Post 标记机——简单的说，其唯一的磁带是无限长度的先进先出队列的有限状态自动机，在每次状态转变中机器读在队列头部的符号，从头部删除固定数目的符号，并可以向尾部增加符号。
1