定义

图灵机是一个 7 元组 ,其中

  • 是状态集合
  • 是输入字母表,表示能够处理的输入字符。特别地,
  • 是工作带字母表,它表示所有能够写在带子上的字母。特别地,,其中 表示输入的起始
  • 是转移函数,其中 表示向左移动, 表示向右移动, 表示不动
  • 是初始状态
  • 是接收状态
  • 是拒绝状态

对于计算问题(而不是判断问题),需要将 合并为

表示图灵机 的字符串编码。

TIP

图灵机可以通过分叉来记住一个枚举值(例如布尔值)。

如果 可以在 时间内可以被一个图灵机判定,则它也可以在 时间内被一个 判定。

带图灵机

带图灵机的定义跟普通图灵机类似,但是每次的输入是 中的元素,状态转移函数也需要同时考虑 条带子的状态。

如果 可以在 时间内被一个 带图灵机判定,则 可在 时间内被一个单带图灵机判定。

如果 可以在 时间内被一个双向纸带图灵机判定,则 可在 时间内被一个单带图灵机判定。

RAM 图灵机

增加一个内存带 和地址带。在 状态下会根据地址带中记载的操作执行操作:

  • 读:将内存带中对应地址的字符读到地址带的当前格子中
  • 写:将内存带的当前格子中的字符写到内存带对应地址上

如果 可以在 时间内被一个 RAM 图灵机判定,则它可以在 时间内被一个多带图灵机判定。此外,如果地址的长度为 可以在 内被多带图灵机判定。

非确定性图灵机

在图灵机的基础上,可以转移到多个状态。

二选一图灵机

在非确定性图灵机的基础上,要求转移到至多两个状态。

通用图灵机

存在一个通用的图灵机 满足对任意 都有 。其中, 表示某个图灵机用 串的编码。

如果 步内结束,则 步内结束。

NOTE

这里 表示 之前的系数由选定的图灵机 决定。