丘奇-图灵论题

2019-05-20  本文已影响0人  WILL_HUNTING

计算机通用模型

4.1 图灵机

图灵机与有穷自动机相似，但图灵机有一个无限存储。

有穷自动机与图灵机之间的区别：

  1. 图灵机在带子上既能写也能读。

  2. 读写头既能向左移动也能向右移动。

  3. 带子是无限长的。

  4. 进入拒绝和接受状态将立即停机。

4.1.1 图灵机的形式定义

定义 4.1一个图灵机是一个7元组(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})其中：Q, \Sigma, \Gamma都是有穷集合，并且：

  1. Q是状态集。

  2. \Sigma 时输入字母表。不包括特殊空白符号\sqcup。

  3. \Gamma是带字母表，其中：\sqcup \in \Gamma, \Sigma \subseteq \Gamma

  4. \delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}是转移函数。

  5. q_0 \in Q是起始状态。

  6. q_{accpet} \in Q 是接受状态。

  7. q_{reject} \in Q 是拒绝状态，且q_{accept} \ne q_{reject}

图灵机计算时，当前状态，当前带内容和读写头当前位置会发生改变，这三项构成的整体叫做图灵机的格局。C1产生格局C2。

定义 4.2 如果有图灵机识别一个语言，则称该语言是图灵可识别的（又称递归可枚举语言）。

判定器

定义4.3 称一个语言是可判定的，如果有图灵机判定它。

图灵可判定语言都是图灵可识别的，反之不成立。

4.1.2 图灵机的例子

  1. 图灵机M1，它检查语言B=\{\omega \sharp \omega \} | \omega \in \{0, 1\}^\star \}

  2. 图灵机M2，它判定语言A=\{0^2^n | n \geqslant 0 \}

  3. 图灵机M3，它判定语言C=\{a^ib^jc^k | i \times j=k, 且i, j, k \geqslant 1 \}

  4. 图灵机M4，它判定语言D=\{\sharp x_1 \sharp x_2 \sharp \cdots \sharp x_l|每个x_i \in \{0, 1\}^\star, 且对任意i \ne j, x_i \ne x_j \}

4.2 图灵机的变形

定义有变化，能力没有改变，这种变化中的不变性成为稳健性。

4.2.1 多带图灵机

4.2.2 非确定型图灵机

4.2.3 枚举器

4.2.4 与其他模型的等价性

4.3 算法的定义

非形式地说，算法是为了实现某个任务而构造的简单指令集。

4.3.1 希尔伯特问题

设计一个算法来测试多项式是否有整数根。这个问题在算法上是不可解的。

D=\{p|p是有整数根的多项式 \}

D是图灵可识别但不是可判定的

4.3.2 描述图灵机的术语

图灵机的输入总是一个串。如果想以一个不是串的对象作为输入，必须先将那个对象表示成串。对象O的编码标识（即串）的记号是<O>。如果有多个对象O_1, O_2, \dots O_k，他们的编码是一个串，记为<O_1, O_2, \dots O_k>

上一篇下一篇

猜你喜欢

热点阅读