Skip to content

Turing Machine

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

图灵机定义

head 可以读写，左右都可以移动；tape 无限长度

image-20241231161718469

halting state 是停机状态，左右箭头就是指，输入了这个符号，将导致状态转移，并且读写头进行相应的一次移动

注意，由于只有左边有 end，右边是无限大的，在右边一定会出现无穷多个连续的空格

image-20241130113108686

图灵机格局（configuration）

image-20241231161842049

image-20241130114147215

计算（设计）图灵机（computation）

基本图灵机

image-20250104192012370

图灵机构建规则

image-20250104192223669

一些常见的基础图灵机及其含义

image-20241215102725492

image-20241215102758678

image-20241215102821902

图灵机功能

Recognize language

判定字符串是，字符串左边会留一个空格作为读写头起点

待判定的字符串内一定不会出现空格

image-20250104194922222

  • 半判定就是，属于的字符串会停机，不属于的字符串不停机
    • recursively enumerable 语言即，存在一个图灵机将其半判定
  • 判定就是，属于的会结束在一个状态，不属于的会结束在另一个不同的状态
    • recursive 语言即，存在一个图灵机将其判定

image-20250104205523155

image-20241215104922039

(abc)^n 也会被接收

Compute function

在字符串函数和数值函数之间构建一个映射即可，可以将数值转化为二进制数字符串

即，一串由 \(\Sigma=\{0,1\}\) 生成的字符串

image-20250104195902422

image-20241215110155313

image-20250104203607468

rec./r.e. 语言性质

递归语言的补集也是递归语言

补集就是把对应的图灵机的 yes 和 no 交换，具体是遍历转移方程，将指向 y 和 n 的交换

image-20250104210136052

rec. 一定是 r.e.

就不让 n 作为停机状态，并让 n 进入死循环即可

image-20241215111149308

两个递归语言的 交集 和 并集 都是递归语言

废话，结果依旧能被两个图灵机判定

变种图灵机

image-20250104211635973

Multiple tape

要求输入的字符串只能放在第一条带，其它带初始是空的

最后的输出也只有第一条带，其它带被忽略

image-20241215112315565

image-20241215112322778

image-20241215112334637

多带图灵机 和 标准图灵机 是等价的

证明： PPT 44 页

非确定性图灵机 NTM

image-20250104212120192

image-20241215115453117

image-20241215115458722

Theorem. Every NTM can be simulated by DTM.

NTM 与 TM 是等价的

PPT 61 页，证明比较难

image-20250104212157811

文法（无限制文法的简称）

Grammar，文法，默认指无限制文法

image-20250104212656053

关键是最后一行，推导关系的左边可以有上下文也可以没有上下文

image-20241215133508957

image-20241215133802340

可以被文法生成 等价于 属于递归可枚举

证明见 PPT 76 页，以及，82~83 页都没讲