图灵机

图灵机(Turing Machine, TM)的组成:

  • 一个有限状态控制器
    • 可以读取符号
    • 可以写入符号
    • 可以左移或右移指针
  • 一条纸带,由有限个单格(cell)组成。可以从上面读写数据。单格可以为空。

image-20210628111158930

形式定义:

$$ M = (Q,T,\Sigma, \delta, q_0, B,F) $$

$Q$: 有限状态集合

$T$:有限输入符号集合 $T \subseteq \Sigma$

$\Sigma$:有限带符号集合

$\delta$:转移函数

$q_0$:起始状态

$B$:空白符 $B\in \Sigma - T$

$F$:终态集合

两个性质:

  1. 每个过程有穷可描述
  2. 过程由离散、可机械执行的步骤组成

转移函数:

$$ \delta:Q\times \Sigma \to Q \times \Sigma \times \{L,R\} $$
function trans(presentState, currentSymbol){
    return [nextState, outputSymbol, movement]
}

例如 $\delta (q,a_i)\to (p,B,L)$,表示现态为 $q$,指针读到 $a_i$,则次态为 $p$,写入空,左移指针。

瞬时描述:$w_1qw_2$,表示正在读 $w_2$ 的第一个符号。$w_1w_2$ 是整个纸带的内容。

一旦进入终止状态,则认为串接受,并停机。

图灵机的停机问题:给定图灵机,是否存在判别程序,能判断该机器对串能否接受。此问题不可判定(无通用解)。

边的格式:$i/o,D$,$i$ 时输入 $o$ 是输出,$D$ 是移动方向。