Undecidability

:material-circle-edit-outline: 约 551 个字 :material-clock-time-two-outline: 预计阅读时间 2 分钟

Church-Turing Thesis

Intuition of algorithms equals (deterministic) Turing machine that halts on every input.

即算法本质上就是图灵机。算法用来解决（判定）问题，而图灵机可以判定语言，二者是等价的。

任何可被“有效计算”的问题都可以由图灵机来计算

• Church-Turing thesis 无法被证明，不是 theorem，是假设，可能被推翻
• 一个算法被定义为一个总能停止（halt）且能返回正确答案的程序
• 一个问题是递归的，则是可判定的；否则是不可判定的
  • 即，存在一个算法能够在有限时间内确定地解决这个问题

编码与判定问题

Universal Turing Machine

基本思想：将图灵机的各部件进行编码，这样就可以编程了

1. 编码字母表里的所有符号，并将四个特殊符号编在最低的位置
   • 用 \(a\) 标识字母表符号，例如 a0001
   • 注意左箭头和右箭头也要，字母表里一般会省略这俩

1. 编码所有的状态，并将起始状态编在最小的位置

   • 用 \(q\) 标识字母表符号，例如 q0001

2. 把转移方程里的符号全替换为编码

如此，我们就把整个图灵机转化为了一串字符串

通用图灵机的表示

我们用 \(U\) 标识通用图灵机，"M" 标识图灵机 M 的编码，"w" 标识字符串的编码

U("M" "w") = "M(w)"

通用图灵机的计算

\(U\) 需要三条 tape，用途如下：

计算步骤：

1. 将 "M" 拷贝到第二条带，并将 "w" 左移至顶，再将 "s" 写到第三条带
2. 我们要模拟 M 的一次计算，方法为：
   • 第一条和第三条带查询第二条带上 M 的编码（转移方程的编码），据此修改第一条带和第三条带的值
3. 重复步骤 2，直到第三条带出现 "h"（halt 状态）
   • 当然可以不会 halt

The Halting Problem

如果一个特定的递归可枚举语言 H 是递归的，那么所有递归可枚举语言都是递归的

r.e. 语言不封闭于 complement 操作，而 rec. 语言封闭于 complement 操作