LearnLog

学习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 QQ
  2. An input alphabet Σ\Sigma
  3. A tape alphabet, which contains Σ\Sigma
  4. A transition function δ\delta
  5. A start state q0q_0
  6. A blank symbol BB
  7. A set of final states F⊆QF \subseteq Q

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

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

类似包含两个栈的PDA?

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

⊢,⊢∗\vdash, \vdash ^*

形式化地, if δ(q,Z)=(p,Y,R)\delta(q, Z) = (p, Y, R), then qZ⊢YpqZ \vdash Yp. And q⊢Ypq \vdash Yp, if Z = Blank
同理: if δ(q,Z)=(p,Y,L)\delta(q, Z) = (p, Y, L), then XqZ⊢pXYXqZ \vdash pXY. And qZ⊢pBYqZ \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.

Programming Trick

Multiple Tracks (多道)

将字符表视为一个元组, 其他按元组处理.
(例如, 处理两个磁道, 此时字符表相当于一个二元组)

Marking

用特殊字符来标记一处位置. 一般用Blank来标记, 但也可以用其他字符
(和Multiple Tracks 结合, 可以用一条纸带来标记其他纸带的某个特殊位置)

Caching in the State (缓存)

  • 状态也可以是一个向量.
  • 第一个分量用于控制, 其他分量用于存储信息 (Turing Maching with Storage)

Simulating Infinite Tape by Semi-infinite Tape:
从起始位置出发, 将纸带分为两部分, 用两个栈进行模拟.

Extension(But still only able to define the same languages.)

  1. Multitape TM: 多条纸带, 同时有多个指针(不同纸带上的移动是独立的)
  2. Nondeteerministic TM: 类似BFS的思想. 能够将一个类似"树"的结构变为线性的.
  3. Store for name-value pairs: #name * value# 其中name, value 都可能是短语. 类似字典的操作, 如Lookup(通过name 查找 value); Insertion, 分类讨论. 当新插入的比旧的长时, 还需要转移其他内容

Simulating k Tapes by One: 使用2k条纸带, 分别记录内容和指针方向; 通过精巧的设计使转移函数等价

因此, 在讨论任意TM时, 我们都可以假设它足够简单
E.g., one, semi-infinite tape, deterministic.
(因为它们是等价的. )

Closure Properties

Closure Properties of Recursive and RE Languages:

  • Both closed under union, concatenation, star, reversal, intersection, inverse homomorphism.
  • Recursive closed under difference, complementation.
  • RE closed under homomorphism.
  • 此处homomorphism和 inverse homomorphism不是成对出现的.

Union / Intersection

构造: 通过2-type TM 构造, "in parallel"地进行函数转移
Recursive languages: 若 M1M_1 和 M2M_2都是algorithms, 则新的 M总会halt (halt性质的保持)
RE languages: 有可能既不halting, 也不 accepting, 永远地run下去. (例如, 原始语言是通过halting来定义accepting的)

对于Recursive TM, 会返回Accept或Reject的结果; 而RE TM, 则只会返回accept的结果(当它halting), 要么就一直不halting地运行下去.
这里按理来说, RE是包含Recursive的, 而不是不交的关系. 但是PPT上好像将两者直接对立起来了

Difference / Complement

由于也是集合运算, 所以是类似上面的逻辑. 不同的是, 需要考虑Recursive / RE.

Recursive languages: both TM’s will eventually halt.

  • Accept if M1 accepts and M2 does not.
  • Corollary: Recursive languages are closed under complementation.
    RE Languages: can’t do it; M2 may never halt, so you can’t be sure input is in the difference.

RE的Union操作同样可能不终止, 为什么没有这个担心呢?
原因: 对于RE语言, 要点在于要将组件的"尚未halting"和结果的"尚未halting"联系起来. 而对于different, 它要求Ahalting的同时, B最终不halting, 此时结果才会halting. 但是我们无法判断B最终halting还是不halting (图灵机停机问题)
相对的, 在前面的Union和Intersection 操作, 我们不需要判断A或B “最终是否halting”, 只需要在尚未halting的时候跟着运行即可.

Concatenation

Recursive languages: 将两个TM首尾相连即可

RE: 构造2-type的非确定性图灵机. 通过非确定性猜测 w = xy的截断点. 然后, 将x, y分别放在两个type上并进行模拟.

Star

Recursive: 挨个尝试将输入 "break into some number of pieces"的划分方法并进行验证.

RE: 通过不确定性 guess many breaks

Reversal

Start by reversing the input. (可以通过一个 2-type图灵机来完成)

对于一个图灵机, 虽然它的纸带是无限长的, 但是它每次接收的输入长度是有限的(例如, NN). 因此, 在做某些类似翻转和切分的操作时, 我们相信它可以在有限时间内完成. (对于无限长的输入, 显然很容易陷入不终止的情况. )

Inverse Homomorphism

已有一个语言 LL, 现在构造一个对应于 h−1(L)h^{-1}(L)的图灵机M

思想: 对于M, 它先做一个 hh操作, 然后进行判断

  • Apply h to input w.
  • Simulate TM for L on h(w).
  • Accept w iff h(w) is in L.
  • Works for Recursive or RE

Homomorphism/RE

已有一个语言 LL, 现在构造一个对应于 h(L)h(L)的图灵机

思想: 对于M, 它先做一个 h−1h^{-1}操作, 然后进行判断.

此处需要借助非确定性的力量, 因为 h−1h^{-1}是 "多到一"的操作. 进行划分的方式可能有很多种. 因此 “won’t work for Recursive languages”.

backtop