图灵机 Turing Machine

TM：人们所接受的算法的形式化描述。与 TM 具有同样计算能力的还有 $\lambda$ 演算、递归函数、波斯特系统等。

定义：七元组 $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$：

  • Q 状态的有穷集合；$\Sigma$ 输入字母表；$\Gamma$ 带符号表（运行过程中的符号）；$q_0$ M 的开始状态；F 终止状态；B 空白符（基本图灵机的概念）；$\delta$ 转换函数，形如 $\delta (q, X) = (p, Y, R 或 L)$，表示在状态 q 读入符号 X，将状态更新为 p，并在 X 所在的方格中印刷符号 Y，接着向右 / 左移动一格。

如：

image-20200902233904457

初始状态下，输入字符串依次放在条带上，指针注释第一个元素，状态为 $q_0$。

TM 定义的语言为递归可枚举语言，即 0 型文法。

TM 即时描述 Instantaneous Description

TM 的即时描述为字符串 $X_1X_2…X_{i-1} qX_iX_{I+1}…X_n$。

  • q：目前状态；磁带指向第 i 个符号
  • 其余符号表示最左侧的空白到最右侧的空白之间的所有字符
  • 同样有 $(\vdash_M)^*, (\vdash_M)^+,(\vdash_M)^n$ 的表达方式以表示特定次数的移动

TM 作为非负整函数的计算模型

对非负整数编码后图灵机具有计算能力。

例如计算 n+m 的图灵机可以将字符串编码为 ${0^m10^n}$，利用图灵机扫描，修改 1 的位置即可。

构造方式

Multiple Tracks 多轨

image-20200903000142831

计算能力和单轨相同，可以将存储的值复合为 {X,Y,Z} 即变成单带。

Subroutine 子图

image-20200903000417382

TM 拓展及变型

Multi-tape Turing machine 多带处理器

image-20200903000545081

本质上也和基本图灵机等价。

Non-deterministic TM 非确定图灵机

对于每一个转移函数 $\delta$，非确定图灵机具有一系列转移结果 ${(q_1,Y_1,D_1),…(q_k,Y_k,D_k)}$

只要有一条路径到达最终状态即可接收。

可计算性 Computability

（仅作了解）

可计算型的问题：对于问题给出是与否的判定。

  • 如果一个问题的语言是递归的，则可判定 Decidable
  • 如果一个问题的语言不可递归，则不可判定 Undecidable

Example:

image-20200903002305978

上述程序查找 $x^n+y^n=z^n$ 的 x, y, z 整数元组，查找到则输出 hello, world。该问题 Undecidable。

img

  • Non-RE language 非递归可枚举语言（一个不能递归枚举字符串中的所有语言）
  • 递归可枚举语言：可以用类似穷举的算法在有限时间内判定一个元素属于该集合
  • 停机问题 Halting Problem: 不存在一个算法，能够判断任意图灵机[公式]在任意字符串[公式]上否停机。
  • 图灵机编码：
    • 用二进制字符串枚举所有可能的字符串（Eg 5337 - 010011011001)
    • image-20200903143418447
    • 接下来对 $\delta$ 编码如下：
      • 对任意 $\delta (q_i, X_j) = (q_k,X_l,D_m)$ 构造字符串 transition = $0^i10^j10^k10^l10^m$，整个图灵机的构造则为 $C_111C_211…C_{n-1} 11C_n$，其中 $C_i$ 为 transition。

NP 与 P

  • P 问题：可以在多项式时间内求解的判定问题 Polynomial Problem
  • NP 问题：Non-Polynomial 不可以在多项式时间内解决的问题
  • NPC 问题：Non-Polynomial Complete NP 中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间的算法，那么所有 NP 问题都是多项式时间可解的。这些问题被称为 NP - 完全问题 (NPC 问题)。