创建 Python 中的图灵机 - 第 1 部分

在本系列中，我想向您展示如何在 Python 中创建一个简单的基于控制台的图灵机。您可以在 https://github.com/phillikus/turing_machine 上查看完整的源代码。

在这一部分中，我将解释图灵机背后的基本理论，并在此基础上设置项目。

要求

• Python 的基础知识
• 理论计算机科学基础

什么是图灵机？

图灵机是一个 计算的数学模型，它基于规则表读取和写入磁带上的符号。每个图灵机都可以通过状态列表和转换列表来定义。 基于起始状态 (s0)，图灵机依次遍历所有状态，直到达到最终状态 (sf)。 如果没有转换导致最终状态，图灵机将“永远”运行，最终会遇到错误。

转换由当前状态、磁带当前位置读取的符号、下一个状态以及必须写入磁带的下一个符号定义。 此外，它还包含一个方向，用于确定磁带头是否应向左、向右移动或根本不移动。 为了可视化此过程，让我们看看一个非常简单的图灵机，它将初始磁带的值递增 1。

一元递增

为了简单起见，我们将从一元图灵机开始。 一个用 '|' 表示。 因此，包含数字 3 的图灵机将如下所示

$|||#

$ 表示我们图灵机的起点，# 表示终点。 递增完成后，我们期望最终磁带看起来像这样

$||||#

要达到最终状态，我们的图灵机只需读取所有 '|' 并附加一个 '|'。

这可以用三个状态 s0、s1 和 sf 以及以下转换来表示

(s0, ‘$’, s1, ‘$’, Right)
(s1, ‘|’, s1, ‘|’, Right)
(s1, ‘#’, sf, ‘|’, Neutral)

也可以用以下状态转换图表示

我们从状态 s0 开始，我们希望读取 '$'。 然后我们切换到状态 s1 并写回 '$'。 然后，我们将磁头向右移动一个字符。

在状态 s1 中，只要我们读取 '|'，我们就会停留在状态 s1 并写回 '|'。 这样，我们将一直移动到磁带的右端。

最后，当我们遇到“#”时，我们写入一个 '|' 并进入最终状态 sf。 由于我们完成了，因此此时没有理由移动磁头。

项目结构

虽然这是一个非常简单的图灵机，但我们可以使用相同的模型来创建任何复杂程度的机器。 有了这些知识，我们现在就可以开始规划我们项目的基本结构了。 为了表示整个图灵机，我们需要一个类，一个用于状态和转换的类，以及磁带。

此外，我们需要一个枚举来表示我们移动图灵机磁头的三个方向：左、右和中性（不移动）。

最后，我们需要一个类来组合所有这些组件并使用它们来处理图灵机。 为每个类添加一个文件后，我得到了以下结构

本系列的第一部分到此结束。 我们现在对图灵机有了基本的了解，并且已经设置了项目。 有了它，现在是开始编码的时候了！ 在本系列的下一篇文章中，我们将实现代码，使我们的图灵机工作，并用上面定义的 Increment 机器来喂它。

感谢您阅读本文。 :) 如果您有任何问题、问题或反馈，请在评论中告诉我。