问题解决：图灵机

来自规范：图灵机和通用机。 图灵机的抽象模型和通用机。

回顾

在尝试学习图灵机之前，您应该确保您熟悉来自 AS 计算规范的有限状态机以及 A2 课程中添加的一些额外的 FSM 概念。

定义

图灵机提供了一种通用的或正式的计算模型，可用于确定某个任务是否可计算。
或者
一种正式的计算模型，它由一个有限状态机 (FSM) 组成，该有限状态机控制一个或多个磁带，其中至少一个磁带具有无限长度（即无限长）。

通用图灵机

通用图灵机 (UTM) 是一种图灵机，它可以通过模拟任何图灵机的行为来执行其他图灵机。如果一个序列是可计算的，那么 UTM 将能够执行它。UTM 的行为就像一个解释器，这正是 PC 在运行 Java applet 或 Flash 脚本时所做的。

UTM 不是在单个机器内处理每个单独的进程，而是接受两个输入

• 执行计算所需的个别图灵机的描述
• 计算所需的所有输入

普遍性原理：通用机是一种能够模拟任何其他机器的机器。

机械图灵机的例子

• 一个“经典风格”的图灵机有一个很棒的视频，描述了物理图灵机的操作。

模拟

• 图灵卡拉有一些很棒的说明，可以帮助您掌握图灵机的基本操作。

示例问题

练习：图灵机 什么是图灵机？ 回答 一个有限状态机，它操作一个或多个磁带，其中至少一个磁带是无限长的。

复习

• 图灵机抽认卡带有测试和其他活动