问题解决：图灵机

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

回顾

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

定义

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

通用图灵机

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

UTM 不像单个机器中的每个单独进程一样，它接受两个输入

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

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

机械图灵机的例子

• 经典风格的图灵机 有一个很棒的视频，展示了物理图灵机的运行。

模拟

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

示例问题

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

复习

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