图灵机简介

图灵机是一种接受设备，它接受由 0 型文法生成的语言（递归可枚举集）。它是由艾伦·图灵于 1936 年发明的。

定义

图灵机 (TM) 是一种数学模型，它由一条无限长的带组成，带被分成单元格，输入放在这些单元格上。它包含一个读取输入带的磁头。一个状态寄存器存储图灵机的状态。读取输入符号后，它会被替换为另一个符号，其内部状态发生变化，并且它从一个单元格向右或向左移动。如果 TM 达到最终状态，则接受输入字符串，否则拒绝。

TM 可以正式描述为一个 7 元组 (Q, X, ∑, δ, q₀, B, F)，其中 -

• Q 是一个有限的状态集

• X 是带字母表

• ∑ 是输入字母表

• δ 是一个转移函数；δ : Q × X → Q × X × {左移, 右移}。

• q₀ 是初始状态

• B 是空白符号

• F 是最终状态集

与先前自动机的比较

下表显示了图灵机与有限自动机和下推自动机的区别。

图灵机的示例

图灵机 M = (Q, X, ∑, δ, q₀, B, F)，其中

• Q = {q₀, q₁, q₂, q_f}
• X = {a, b}
• ∑ = {1}
• q₀ = {q₀}
• B = 空白符号
• F = {q_f }

δ 由下表给出 -

这里转移 1Rq₁ 表示写入符号为 1，磁带向右移动，下一个状态为 q₁。类似地，转移 1Lq₂ 表示写入符号为 1，磁带向左移动，下一个状态为 q₂。

图灵机的时空复杂度

对于图灵机，时间复杂度是指当机器为某些输入符号初始化时磁带移动次数的度量，空间复杂度是指写入的磁带单元格数。

所有合理函数的时间复杂度 -

T(n) = O(n log n)

TM 的空间复杂度 -

S(n) = O(n)