非确定图灵机 编辑
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为
3
图片 0 图片
评论 0 评论
匿名用户 · [[ show_time(comment.timestamp) ]]
[[ nltobr(comment.content) ]]
相关
线性有界自动机是受限形式的非确定图灵机。它拥有由包含来自有限集合字母表的符号的单元构成的磁带，可以一次读取和写入磁带上一个单元的并可以移动的磁头，和有限数目个状态。它区别于更为普遍的图灵机在于尽管磁带最初被认为是无限的，只有其长度是初始输入的线性函数的有限临近部分可以被读写磁头访问。这个限制使 LBA 成为在某些方面比图灵机更接近实际存在的计算机的精确模型。