什么是可计算性理论(Computability Theory)
可计算性理论使我们我们承认, 计算机不能解决所有问题, 由此引发了我们对可计算性的思考:
使用理论上能制造的机器, 什么样的问题可以被计算解决?
从某种角度来说, 计算机科学可以理解为用机器解决问题的学问, 当我们从理论角度探讨这门学问的时候, 自然而然的, 就会有以下问题:
- 如何定义
机器? - 如何定义
问题?
依照惯例, 当我们试图从理论上解决一个问题的时候, 我们需要一个数学模型, 这个模型可以很好的模拟现实问题, 同时又忽略了现实问题的可忽略复杂性
当我们研究如何定义机器这个问题的时候, 我们的模型就是自动机(Automata)
当我们研究如何定义问题这个问题的时候, 我们的模型是形式语言(Formal Language)
有限自动机(Finite Automata)
FA 是一种对有限内存机器的建模, 这样每一个实际机器都可以抽象为一台理论的FA
使用FA这个模型, 我们可以把机器解决问题理解为有限数量的状态转移, 类似于:
提出问题 -> 转化问题(可以有若干步骤) -> 解决问题
数学上, 5-tuple 定义很好的阐释了FA的特征
A finite automaton is a 5-tuple ($Q$,$\Sigma$, $\delta$,$q_0$, $F$)
- $Q$ is a finite set called the states
- $\Sigma$ is a finite set called the alphabet
- $\delta$: $Q \times \Sigma \rightarrow Q$ is the transition function
- $q_0 \in Q$ is the start state
- $F \subset Q$ is the set of accept states
很多现实中的 programming problem 也是用状态机模型解决的, 例如TCP状态转移, 电商应用的订单状态, App的生命周期…
DFA 和 NFA
上述FA的定义也是 DFA (Deterministic Finite Automata) 的定义, 我们可以看到对于给定的状态$Q$, 其下一 state 是唯一确定的, 亦即函数$\delta$返回一确定值
如果我们允许$\delta$ 返回多个states, 亦即 $\mathcal{P}(Q)$, 这样我们得到的FA 称为 NFA(Nondeterministic Finite Automata), NFA 可以看作是可以并行计算的 DFA
用 5-tuple 来定义:
A finite automaton is a 5-tuple ($Q$,$\Sigma$, $\delta$,$q_0$, $F$)
- $Q$ is a finite set called the states
- $\Sigma$ is a finite set called the alphabet
- $\delta$: $Q \times (\Sigma_\epsilon) \rightarrow \mathcal{P}(Q)$ is the transition function
- $q_0 \in Q$ is the start state
- $F \subset Q$ is the set of accept states
正则语言 (Regular Language) 和 正则表达式 (regular expression)
由上面两个 FA 的定义, 我们可以看出一个给定的 FA 和 一个输入的 string 其终止状态 只有两种可能 accept 或 reject, 于是我们发现每一个 FA 总是对应着一个 language(a set of acceptable string), 这就是 Regular Language.
Regular Language 有很多数学上很棒的特性, 列举如下
先假设集合$RL$是所有的Regular Language \[L_1 \in RL \land L_2 \in RL \rightarrow L_1 \cup L_2 \in RL\] \[L_1 \in RL \land L_2 \in RL \rightarrow L_1 \cap L_2 \in RL\] \[L_1 \in RL \land L_2 \in RL \rightarrow L_1L_2 \in RL\] \[L \in RL \rightarrow L* \in RL\]
于是, 给定若干简单的Regular Language, 我们可以用上述的操作来构造复杂的Regular Language, 由此我们可以用一种新的语言来描述这个过程, 这就是正则表达式(regular expression)
理论上的正则表达式(和实际中使用的那种不同), 是一种自底向上构造 Regular Language 的方式, 于是我们有一个数学上的 induction definition
Say that $R$ is regular expression if $R$ is
- $a$ for some $a$ in alphabet $\Sigma$
- $\epsilon$
- $\emptyset$
- $R_1 \cup R_2$ where $R_1$ and $R_2$ is regular expression
- $R_1 R_2$ where $R_1$ and $R_2$ is regular expression
- $R_1*$ where $R_1$ is regular expression
关于DFA, NFA, regular expression, 我们可以从数学上证明, 给定任意一个automaton, 我们一定可以将其转化为另外的两种形式, 也就是说以下命题等价
$L$ is a regular language.
There is a DFA $D$ such that ℒ($D$) = $L$.
There is an NFA $N$ such that ℒ($N$) = $L$.
There is a regular expression $R$ such that ℒ($R$) = $L$.
图灵机 (Turing Machine)
对于计算来说, FA的问题在于抽象程度并不够好,于是主要应用于模式匹配(正则表达式)问题
所以我们希望有一类模型, 它足够灵活简单, 可以应用在比较广泛的问题领域中, 同时我们要求它的算力不能弱于现实中的机器, 它就是著名的图灵机模型, 图灵机模型是一种内存无限的自动机, 如果我们能证明某个理论问题可以被图灵机解决, 我们自然可以推出, 这个问题对应的现实问题(现实问题常常不需要无限的内存, 所以它可以看作是理论问题的弱化版本)可以被现实机器解决;相反的, 如果某个问题我们可以证明不能被图灵机解决, 那我们可以自信地用理论来指导实践, 这个问题一定不能被现实机器解决.由此观之, 图灵机模型虽然超越现实, 但它确实有很强的现实意义.
图灵机(TM)可以看作是一种比FA复杂的automaton, 我们有一个类似但是更复杂的7-tuple定义:
A Turing machine is a 7-tuple, ($Q$, $Σ$, $Γ$, $δ$, $q_0$, $q_{accept}$, $q_{reject}$), where $Q$, $Σ$, $Γ$ are all finite sets and
- $Q$ is the set of states,
- $Σ$ is the input alphabet not containing the blank symbol $␣$,
- $Γ$ is the tape alphabet, where$␣$∈ $Γ$ and $Σ$ ⊆ $Γ$,
- $δ$: $Q \times Γ \rightarrow Q \times Γ \times {L,R}$is the transition function,
- $q_0$ ∈ $Q$ is the start state,
- $q_{accept}$ ∈ $Q$ is the accept state, and
- $q_{reject}$ ∈ $Q$ is the reject state, where $q_{reject} \ne q_{accept}$.
递归语言(R) 和 递归可枚举语言(RE)
和FA不同的是, 图灵机的运行结果有三种, accept,reject 或 loop, loop很像现实中的计算机, 可以给定一个输入使得图灵机陷入死循环, 根据一个图灵机是否会loop ,我们把图灵机对应的language 分为两种
- 任意一个图灵机对应的称为 RE(recursively enumerable language), 递归可枚举语言, 我们也称这种机器为recognizer
- 对于任意输入都不会loop的称为 R(recursive language), 递归语言, 我们也称这种机器为decider
关于这两个奇怪的名字, 其实他们是来源于一些早期的数学研究, 在理论CS领域里已经失去了本名的意义, 如书上说:
These may seem like odd names—what does recursion have to do with TMs? But it turns out that these two sets of languages were independently identified by a number of different researchers working in different areas of mathematics. Although we are defining these sets in terms of TMs, the standard names come from mathematical studies of computability using the theory of recursive functions.
邱奇-图灵论题(Church-Turing thesis)
回到本文开始的问题:
使用理论上能制造的机器, 什么样的问题可以被计算解决?
显然这是一个无法数学界定的问题, 一个问题是否能被解决受限于我们能给出的算力成本(时间,空间和其他现实而丑陋的成本)
关于这个无法界定的问题, 我们不太关心它能否被解决, 而是更关心能否在限定算力下解决, 在限定算力下解决学界称为“Effective Computation”, 著名的Church-Turing thesis把 effective 定义为decider能解决的问题, 也就是说, 一般在理论上无限内存有限时间上可以 Effectively 解决的问题, 也可以在现实中解决, 这对应了我们前述说法, 理论上需要无限内存的问题往往在现实中对应着有限的内存需求, 随着科技与算力的发展, 这些问题是将来可预见被解决的(摩尔定律),
可以让decider解决的问题我们又称为 Turing Computable
Church-Turing thesis同时了勾勒出我们对算法的一般预期, 一般我们认为算法都是对应一个decider的, 也就是说, 使用预先定义的有限步骤(机器)在合理成本(Effectively)下解决问题的方法
不可决定的问题(Undecidable Problem)
遗憾的是, 算法不能解决所有问题, 因为如果我们假设算法能解决所有问题, 便会陷入自相矛盾当中去, 我们可以用self-reference的思想来思考著名的停机问题:
是否存在一台 decider $HALT$ , 它可以判断任意图灵机是否是decider ?
我们可以思考, 假设有这么一台图灵机 $M$ 存在 ,那么我们就可以构造一台图灵机 $N$, 输出和 $M$ 相反的答案, 于是我们陷入了自相矛盾:
如果我们假设 $M$ 存在, 我们就能构造出$M$无法判定的图灵机, 于是$M$不存在
但是显然的, $HALT$ 是一台recognizer, 我们只需要用$HALT$来模拟输入的图灵机即可
这也说明: 有些问题的答案, 是不可决定的, 我们无法推测答案是否存在, 唯一的方法是实践
结语
RE之外, 是 Unrecognizable Language, Unrecognizable Problem的存在说明有些问题存在但不存在解决问题的方法
关于开篇的问题, 可以得出, 可计算理论告诉我们
使用理论上能制造的机器, 我们只能在有限算力下解决图灵机能解决的问题