图灵机 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 问题)。