什么是理论计算机科学中的图灵机？

图灵机是一种计算模型，类似于有限自动机 (FA)、下推自动机 (PDA)，它基于无限制文法工作。与 FA 和 PDA 相比，图灵机是最强大的计算模型。

正式地，图灵机 M 可以定义如下：

M = (Q, X, ∑, δ, q0, B, F)

• Q 表示有限的、非空的状态集。

• X 表示带字母表。

• ∑ 表示非空的输入字母表。

• δ 是转移函数，其映射关系为 δ : Q x X → Q x X x {左移, 右移}。

• q0 是机器的初始状态。

• B 是空白符号。

• F 是最终状态集或停机状态集。

单带图灵机有一个无限长的单带，它被分成若干个单元格。

这些单元格中包含带符号。

存在一个有限控制器，它根据给定的输入控制图灵机的运行。

有限控制器有一个读/写头，它指向带上的一个单元格。

图灵机可以从一个单元格左右移动到另一个单元格。

输入和输出带符号

↑

有限控制器

图灵机对输入可以有三种类型的动作。

打印 Si，左移一个方格 (L)，并转到状态 qj。

打印 Si，右移一个方格 (R)，并转到状态 qj。

打印 Si，不移动 (N)，并转到状态 qj。

Bhanu Priya

更新于：2023年9月14日

32K+ 次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习