[Automata] Ch8 图灵机 TM

学习Automata PPT的记录. 相关笔记会另开博客记录. 也可能不会开.

Turing-Machine Theory

The purpose of the theory of Turing machines: 证明某个特定的语言没有算法

通过reductions来证明许多常见问题的不可判定性.

Turing-Machine Formalism

A TM is described by:

1. A finite set of states $Q$
2. An input alphabet $\Sigma$
3. A tape alphabet, which contains $\Sigma$
4. A transition function $\delta$
5. A start state $q_0$
6. A blank symbol $B$
7. A set of final states $F \subseteq Q$

The Transition Function:
对于接受一个状态和一个输入符号的 $\delta (q, Z)$, 它要么为定义, 要么返回一个 $(p, Y, D)$. p是一个状态, Y是新的符号, D是一个方向

Instantaneous Descriptions of a Turing Machine:
广义状态: 包含一串输入符, 同时认为其左右都是Blank; 包含一个状态, 类似指针.

类似包含两个栈的PDA?

接着定义 “one move” "zero or more moves"的概念, 是类似的递归定义

$$\vdash, \vdash ^*$$

形式化地, if $\delta(q, Z) = (p, Y, R)$, then $qZ \vdash Yp$. And $q \vdash Yp$, if Z = Blank
同理: if $\delta(q, Z) = (p, Y, L)$, then $XqZ \vdash pXY$. And $qZ \vdash pBY$, if Z = Blank

A TM defines a language by final state, or by halting.
且, 这两种定义方式是等价的. 类似 NPDA.

此处需要注意的是, 在final states的定义下, TM开始运行后只要经过了终止状态, 就算被接受了(即使在经过之后又转移走了然后不断运行其他状态)

If L = L(M), then there is a TM M’ such that L = H(M’).
If L = H(M), then there is a TM M” such that L = L(M”).

Proof:

1. 通过final state定义的language能通过halting来定义: 对于所有的final states, 去除他们的move; 同时, 为了防止accidentally halt, 设置一个保护状态s, 所有的非定义函数都会转移到这个状态, 且它永不停止地往右读
2. 通过halting定义的language也能通过final states来定义: 对于所有halting的情况, 转移到一个final state, 且它没有转移; 同时为了防止意外的final states, 将原有的final states除去,

This class of languages is called the recursively enumerable languages.
An algorithm is a TM, accepting by final state, that is guaranteed to halt whether or not it accepts.
If L = L(M) for some TM M that is an algorithm, we say L is a recursive language.
此处两种语言有些许不同, 需要注意.

算法是一个TM, 通过终止态接收.
换言之:

• 若算法在终止前经过了终止态, 那么它接收对应的输入
• 若算法在终止前没有经过终止态, 那么它拒绝对应的输入.

于是, 比起通过halting来定义的TM (在不接收时不终止), 一个算法总是会halting.

Ex:

• Every CFL is a recursive language (Use the CYK algorithm)
• Almost anything you can think of is recursive.