C# 图灵机

• 可执行文件 - 22 KB
• 下载源代码 - 39 KB

介绍 

图灵机是计算的理论模型。它们不像我们通常认识的计算机那样具有实际应用。它们是研究理论计算领域问题的工具。数学家艾伦·图灵（Alan Turing）创建它们是为了描述计算是什么，以便当时的数学家能够解决需要对算法进行正式描述的抽象问题，而算法的概念在当时并没有真正明确。顺便说一句，他恰好帮助创造了我们今天所知的计算机。与此同时，另一位数学家阿隆佐·丘奇（Alonzo Church）也独立地找到了“计算是什么意思？”这个问题的答案，但他的表述形式是一个称为 lambda 演算的形式系统。  

图 1：艾伦·图灵和阿隆佐·丘奇 

背景 

每台计算机都等价于一台图灵机，反之亦然，任何图灵机都可以计算任何其他计算机能计算的东西。也许这是它们最令人惊叹的事实之一：作为一种非常简单的机器，一台图灵机理论上，只要有足够的时间和资源，就可以运行你在计算机上能运行的任何东西，任何算法。一台小型机械图灵机，例如后面描述的那一台，可以完全模拟你现在阅读这篇文章时所用的计算机，包括所有的软件、操作系统，甚至是硅芯片的功能。更确切地说，通常将图灵机用作其他系统/机器进行比较的基础计算设备，因此如果我们说前者与图灵机兼容，那么我们就意味着它具有计算或执行任何可计算函数的能力。

图 2：模拟器的屏幕截图 

图灵机描述 

早在 20 世纪 30 年代，人们通常认为这种机器可能是电气/机械的，甚至是纯粹的机械的，因为那时电子技术还没有那么普及。一台图灵机可能由以下部分组成： 

1. 一个可以存储符号的磁带。起初，可以认为这是一维磁带，符号沿着磁带并排存储。在磁带上的某个位置写入符号的方法可能类似于使用磁记录设备（磁头）。 
2. 一组有限的符号，即符号字母表，在我们的例子中是数字 {0,1,2...n} 
3. 磁头：一个设备，用于读取和写入磁带上给定位置的符号，并能够向左或向右移动一个位置。 
4. 一个名为“状态”的变量，它表示机器的当前状态。可能的状态构成一个有限的符号集，在我们的例子中是字母 {A, B, C 等}。状态和正在读取的符号决定了磁头将执行的下一步操作。给定读取到的符号和当前状态，机器会在磁带的当前位置打印另一个符号，将磁头向左或向右移动，并改变其状态。一个名为“停止”（HALT）的特殊状态，当机器最终达到该状态时，机器将停止，计算也随之结束。所有这些指令都可以排成一个表。 

图灵在他的原始论文 [http://plms.oxfordjournals.org/content/s2-42/1/230] 中也这样描述它，就像我们手动在纸上写符号（然后一个人可以遵循状态表中描述的规则，这样他/她就可以手动计算相同的东西）。 

图 3：图灵机描述。 

例如，考虑以下指令：“如果磁头在磁带上的当前位置 P 读取到符号 1，并且当前状态是 A，那么写入符号 0，磁头向左移动，并转到状态 B”。这个指令可以用伪代码表示为：

If read(p)=1 and state=A Then {  
  Print(0,p);
  P=P-1; 
  state=B;
}

因此，上面 {} 中的指令可以由当前读取到的符号和当前状态作为索引。如果我们构建一个表格，其中行表示读取到的符号 0,1,2...n，列表示可能的状态 A, B, C 等，那么我们可以在表格的每个单元格中以编码的形式存储要执行的指令，例如，“P0,L,B”（对于上面的例子）或“P1,R,A”，始终表示“打印，移动到...，转到状态...”。在当前的模拟器中，有一个 DataGridView 控件中有这样一个表格，用户可以通过点击单元格手动编辑表格，来修改/创建一台新机器。我们保留字母 Z 作为 HALT 状态，即当遇到字母 Z 时，机器停止。机器可以被概括为在一个持续的循环中执行这些指令，直到遇到 HALT 指令（或者如果它从未被遇到，机器将永远循环）。 

图 4：状态表示例（上方）及其在 DataGridView 中的编码（下方）。 

就这样。给定一台根据状态表中的指令构建的机器，机器将开始运行，并在磁带上写入一些符号集。我们可以巧妙而谨慎地编写一个“程序”（即状态表）来在一定程度上写出我们想要的符号字符串。结果可能是一些计算，结果字符串代表某个数字。在其他情况下，我们几乎可以随机选择一个状态表，而事先不知道机器会在磁带上写什么，甚至不知道是否会达到 HALT 状态。 

因此，在可计算性理论中，图灵机被用作计算的抽象模型。存在与计算、形式系统、元数学等相关的基本问题，这些问题可以通过图灵机来表述。我提到了一个著名的“停机问题”

[http://en.wikipedia.org/wiki/HALTing_problem] 

另一个是匈牙利数学家蒂博尔·拉多（Tibor Radó）在 60 年代提出的一个引人入胜的“游戏”：“忙碌的 the Beaver 游戏”[http://en.wikipedia.org/wiki/Busy_beaver]。如维基百科文章所述： 

“在可计算性理论中，忙碌的 the Beaver（来自粗俗的‘勤奋的人’的说法）是一台图灵机，它在某一类图灵机中达到最大的‘操作忙碌度’（例如，以执行的步数或最终磁带上的非空白符号数量来衡量）。这一类的图灵机必须符合特定的设计规范，并且在用空白磁带启动后必须最终停止。 

忙碌的 the Beaver 函数量化了给定类型的“操作忙碌度”的上限，并且是一个不可计算函数。事实上，可以证明忙碌的 the Beaver 函数的渐近增长速度比任何可计算函数都要快。这个概念最早由蒂博尔·拉多在他的 1962 年论文《论不可计算函数》中作为“忙碌的 the Beaver 游戏”提出。” 

通常人们说，具有特定状态表和规则的图灵机，其配置主要由状态的数量和符号的数量来描述。例如，运行忙碌的 the Beaver 函数的配置可以表示为 BB(4,2)，表示一个具有 4 个状态和 2 个可读/写符号的图灵机程序（函数）。请注意，也可以构建许多具有不同规则但都具有 4 个状态和 2 个符号的状态表。忙碌的 the Beaver 函数是在该配置类别中产生磁头移动最大数量或磁带上符号最大数量的函数。拉多提出的游戏是找出每种可能的状态数和符号数组合中，哪种配置能给出该类别 BB 函数的值。 

值得一看斯科特·阿伦森（Scott Aaronson）有趣的论文“谁能说出更大的数字？”[http://www.scottaaronson.com/writings/bignumbers.html] 

模拟器  

此图灵机模拟器仅用于教育和教学目的。它并非以速度为设计目标，顺便说一句，由于屏幕绘图代码的执行，速度有所降低。另一方面，模拟器采用了一种方式来利用 .NET Framework 的一些出色功能：整个机器都包含在 TuringMachine.cs 类中。这个类公开了机器配置和状态的属性，然后我们使用 PropertyGrid 控件将 TuringMachine 对象绑定到控件上，以在屏幕上显示属性。此外，TuringMachine.cs 类具有一组事件，这些事件由应用程序 Form 中的处理程序处理，以捕获与机器相关的事件：磁头移动、停止、处理、开始、磁带重置和异常处理程序（例如，如果机器到达磁带末尾）。用户可以通过修改 PropertyGrid 中的值来交互式地更改机器的属性。 

主 Form 有一个工具栏，提供了一些有用的功能：状态表（实际上是图灵机的“程序”）可以从磁盘保存和检索。用户可以编辑状态表 DataGridView，以修改/创建新机器。 

TuringMachine 类具有类似于编译器中常见“调试模式”的功能：  

1. 在工具栏的 ComboBox 中选择一些示例状态表（例如：“Busy Beaver 4,2”）。 
2. 在 PropertyGrid 中将“StepThrough”属性更改为“True”。 
3. 点击“Run”按钮。机器启动，但每一步都应该由用户通过点击“Step into”按钮来触发。 
4. 可以随时点击“Pause/Continue”按钮来恢复正常执行。 

这种逐步执行模式，加上磁带、磁头的图形显示以及状态表 DataGridView 上的高亮显示，有助于用户深入了解图灵机的工作原理。 

每台图灵机都有一个状态表。TuringMachine.cs 类在一个 ArrayList 对象中保存状态表，其中每一行都包含在读取磁带上的符号 0,1,2,3 等情况下的操作指令，被用作表格行的索引的符号。图 5 展示了如何使用 ArrayList 创建一个状态表。  

  

图 6：TuringMachine 类。 

当机器运行时，TuringMachine 对象触发的事件会被 Form 对象中的处理程序拦截。然后，涉及的绘图代码会更新屏幕上的机器绘图，即磁带和磁头绘图、磁带内容等。绘图代码更新长磁带花费的时间更长，但如果应用程序被最小化，并且绘图没有显示在屏幕上，速度会大大提高。此外，系统托盘图标会显示，以告知用户模拟器正在运行，用户点击此图标会再次最大化应用程序。 

创建机器 

创建新机器的描述只需要几行代码： 

1. 实例化一个 TuringMachine 对象（在 Form1.cs 的 frmMain_Load() 方法中完成。检查 CreateEmptyMachine() 方法。此方法还将 TuringMachine 对象绑定到 PropertyGrid 控件）。
2. 设置机器的属性。
3. 添加状态表
4. 将状态表 ArrayList 绑定到 DataGridView
5. 运行应用程序并点击“Run”按钮。机器将被准备好，并调用 TuringMachine 对象上的 StartMachine() 方法。 

代码可以类似于以下摘录（假设我们已经有一个名为 TM 的对象，它是 TuringMachine.cs 的一个实例。在此示例中，状态表是图灵机忙碌的 the Beaver 游戏程序的一种形式）

TM.NumberOfstates = 6;
TM.Name = "Busy Beaver 6 states 2 symbols";
TM.FillSymbol = "0";
TM.Initialstate = "A";

ArrayList stateTableBB62 = new ArrayList();

stateTableBB62.Add(new stateTableRow(
                0,
                "P1,R,B",
                "P0,R,C",
                "P1,L,D",
                "P0,L,E",
                "P0,R,A",
                "P1,L,A",
                    "",
                    "",
                    "",
                    "",
                    "",
                    ""
                ));

            stateTableBB62.Add(new stateTableRow(
                1,
                "P0,L,F",
                "P0,R,D",
                "P1,R,E",
                "P0,L,D",
                "P1,R,C",
                "P1,R,Z",
                    "",
                    "",
                    "",
                    "",
                    "",
                    ""
                ));

dataGridView1.DataSource = stateTableBB62;
// This method reshapes the dataGridView to show the correct numbers of columns and rows
RedefineNumberOfstates(TM);


// Some possible code, on the Form1.cs class, to prepare and start the machine:

FillTape(TM.FillSymbol);
TM.Currentstate = TM.Initialstate;
TM.CurrentTapePosition = TM.TapeLength / 2;

// These two methods are part of the drawing methods group inside Form1.cs
MoveHeadOnScreenTo(TM.CurrentTapePosition);
MoveStartMarkerOnScreenTo(TM.CurrentTapePosition);

TM.stateTable = (ArrayList)dataGridView1.DataSource;
TM.StartMachine();