图灵机 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,接着向右 / 左移动一格。
如:
初始状态下,输入字符串依次放在条带上,指针注释第一个元素,状态为 $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 多轨
计算能力和单轨相同,可以将存储的值复合为 {X,Y,Z} 即变成单带。
Subroutine 子图
TM 拓展及变型
Multi-tape Turing machine 多带处理器
本质上也和基本图灵机等价。
Non-deterministic TM 非确定图灵机
对于每一个转移函数 $\delta$,非确定图灵机具有一系列转移结果 ${(q_1,Y_1,D_1),…(q_k,Y_k,D_k)}$
只要有一条路径到达最终状态即可接收。
可计算性 Computability
(仅作了解)
可计算型的问题:对于问题给出是与否的判定。
- 如果一个问题的语言是递归的,则可判定 Decidable
- 如果一个问题的语言不可递归,则不可判定 Undecidable
Example:
上述程序查找 $x^n+y^n=z^n$ 的 x, y, z 整数元组,查找到则输出 hello, world
。该问题 Undecidable。
- Non-RE language 非递归可枚举语言(一个不能递归枚举字符串中的所有语言)
- 递归可枚举语言:可以用类似穷举的算法在有限时间内判定一个元素属于该集合
- 停机问题 Halting Problem: 不存在一个算法,能够判断任意图灵机
在任意字符串
上否停机。
- 图灵机编码:
- 用二进制字符串枚举所有可能的字符串(Eg 5337 - 010011011001)
- 接下来对 $\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 问题)。