计算理论导引 (4-丘奇-图灵论题)
丘奇-图灵论题
有穷自动机能较好地描述计算资源较少的设备，下推自动机虽然能描述具有无限存储的设备，但“后进先出”的栈机制使其能力受到限制，还证明了这些模型对于有些非常简单的任务都不能完成，由于它们过于局限，因此不能作为计箅机的通用模型。
图灵机
图灵机(Turing Machine)与有穷自动机相似，但它有无限大容童的存储且任意访问内部数据。图灵机是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为。
有穷自动机与图灵机之间的区别：
- 图灵机在带子上既能读也能写。
- 图灵机的读写头既能向左也能向右移动。
- 图灵机的带子是无限长的。
- 图灵机进入拒绝和接受状态将立即停机。
图灵机的形式化定义
图灵机 是一个7元组$(Q,Σ,Γ,δ,q0,q{accept},q_{reject})$，其中$Q,Σ,Γ$都是有穷集合,并且
- $Q$是状态集。
- $Σ$是输入字母表,不包括特殊空白符号$␣$。
- $Γ$是带字母表,其中:$␣∈Γ,Σ⊆Γ$。
- $δ：Q×Γ→Q×Γ×{L,R}$是转移函数。
- $q_0∈Q$是起始状态。
- $q_{accept}∈Q$是接受状态。
- $q{reject}∈Q$是拒绝状态,$q{reject}≠q_{accept}$。
如果一个语言能被某一图灵机识别，则称该语言是 图灵可识别的（Turing-recognizable) 或 递归可枚举语言
图灵机的变形
多带图灵机
每个多带图灵机等价于某一个单带图灵机。
非确定型图灵机
非确定型图灵机有如其名：在计算过程中，机器可以在多种可能性动作中选择一种继续进行。
每个非确定型图灵机都等价于某一个确定型图灵机。
枚举器
一个语言是图灵可识别的，当且仅当存在枚举器枚举它。
与其他模型的等价性
人们还提出了许多其他的通用计算模型，其中的一些与图灵机十分相似，而另一些则相差甚远，但都具有图灵机的本质特征，即 可以无限制地访问无限的存储器，这个特征把它们和有穷自动机、下推自动机等能力较弱的模型区别开来。值得注意的是，已经证明：具有此特点的所有模型在能力上都是等价的，只要它们满足一些合理的必要条件(例如，在一步中只能执行有限的工作)即可。
虽然计算模型是多种多样的，但它们所描述的算法类只有一个。单个计算模型的定义有一定的随意性，但从根本上说它所描述的算法类是自然的，因为它和其他模型所描述的类是一样的。这种现象对于数学也有深远的意义。
算法的定义
希尔伯特问题
描述图灵机的术语
图灵机算法的描述方式标准化:
- 形式化描述，即详尽地写出图灵机的状态、转移函数等，这是最低层次、最详细程度的描述
- 实现描述 ，这种方法使用日常语言来描述图灵机的动作，如怎么移动读写头、怎么在带上存储数据等，这种程度的描述没有给出状态和转移函数的细节
- 高水平描述 它也是使用日常语言来描述算法，但忽略了实现的模型，这种程度的描述不再需要提及机器怎样管理它的带子或读写头。
Chomsky hierarchy
转载请注明：转载自srzyhead的博客(https://srzyhead.github.io)
本文链接地址: 计算理论导引 (4-丘奇-图灵论题)
