python图灵机_用python模拟图灵机并在其上执行程序

<article style="font-size: 16px;">
<p>python图灵机</p>
<div>
  <section>
<div>
<div>
   <p>In this article, we shall implement a basic version of a Turing Machine in python and write a few simple programs to execute them on the Turing machine. This article is inspired by the <strong>edX / MITx course Paradox and Infinity </strong>and few of the programs to be executed on the (simulated) Turing machine are taken from the course. Also, some programs are from this <a href="https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/four.html">Cambridge tutorial</a>.</p>
   <p>在本文中，我们将使用python实现图灵机的基本版本，并编写一些简单的程序在图灵机上执行它们。本文受到<strong>edX / MITx课程Paradox和Infinity的</strong>启发，该<strong>课程中</strong>几乎没有要在(模拟的)图灵机上执行的程序。另外，有些程序来自此<a href="https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/four.html">Cambridge教程</a>。</p>
   <h1> 一些定义 <span style="font-weight: bold;">(</span>A few Definitions<span style="font-weight: bold;">)</span></h1>
   <p>Let’s start by defining a Turing machine (originally invented by <strong>Alan Turing</strong>) formally, as is shown in the following figure:</p>
   <p>让我们首先正式定义图灵机(最初由<strong>Alan Turing</strong>发明)，如下图所示：</p>
   <p>In this article, we shall assume that the tape alphabet can contain only the <strong>symbols {0,1,}</strong>, the head on the Turing machine moves in left (L) / right (R) direction (D) or doesn’t move (*), upon reading a symbol on the tape (i.,e., <strong>D</strong> can be one of <strong>{L,R,*}</strong>). Also, given a <strong>program</strong> along with a valid <strong>input</strong>, the Turing machine just halts (goes to the state <strong>halt</strong>) after writing the desired <strong>output</strong> on its tape.</p>
   <p> 在本文中，我们将假设磁带字母只能包含<strong>符号{0,1，}</strong> ，图灵机上的头向左(L)/右(R)方向(D)移动或不移动(*)，在读取磁带上的符号时(即<strong>D</strong>可以是<strong>{L，R，*}之一</strong>)。此外，与有效<strong>输入</strong>沿给定的<strong>程序</strong>，图灵机只是暂停其磁带写入所需的<strong>输出</strong>后(进入状态<strong>停止</strong>)。</p>
   <h1> 模拟图灵机的python实现 <span style="font-weight: bold;">(</span>The python implementation for simulating a Turing Machine<span style="font-weight: bold;">)</span></h1>
   <p>The following python code shows a very simple implementation of a Turing machine. It accepts a program as a string, with each transition function defined on a new line. The state <strong>halt</strong> is denoted by <strong>H</strong>.</p>
   <p>以下python代码显示了图灵机的非常简单的实现。它接受一个程序作为字符串，每个转换函数都在新行中定义。状态<strong>停止</strong>由<strong>H</strong>表示。</p>
   <figure style="display:block;text-align:center;">
   <div>
   <div>
      <div>
      <div>
      <div style="text-align: center;">
         <img alt="Image for post" height="811" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-8c2272b06d3da32b1051c33c682de90c.png" style="outline: none;" width="818">
      </div>
      </div>
      </div>
   </div>
   </div>
   </figure>
   <p>In the next section we shall show how a program on this Turing Machine will look like and how to run such a program, by instantiating the above class. We shall demonstrate with a few programs.</p>
   <p> 在下一节中，我们将通过实例化上述类来展示该Turing Machine上的程序的外观以及如何运行该程序。我们将通过一些程序进行演示。</p>
   <h1> 1.用图灵机进行二进制加法 <span style="font-weight: bold;">(</span>1. Binary Addition with Turing Machine<span style="font-weight: bold;">)</span></h1>
   <p>The following figure shows how to perform binary addition with a Turing machine, where the binary numbers to be added are input to the Turing machine and are separated by a single blank. The TM header is assumed to be positioned at the leftmost position of the first number, in the very beginning.</p>
   <p>下图显示了如何使用图灵机执行二进制加法，其中要添加的二进制数输入到图灵机，并用单个空格分隔。假设TM标头从一开始就位于第一个数字的最左侧位置。</p>
   <figure style="display:block;text-align:center;">
   <div>
   <div>
      <div>
      <div style="text-align: center;">
      <img alt="Image for post" height="433" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-33ff2458271a114a7e7531d2a6703e65.png" style="outline: none;" width="236">
      </div>
      </div>
   </div>
   </div>
   <figcaption>
   <a href="https://courses.edx.org/courses/course-v1:MITx+24.118x+2T2020/course/">source</a>)
   <a href="https://courses.edx.org/courses/course-v1:MITx+24.118x+2T2020/course/">源</a>)
   </figcaption>
   </figure>
   <p>The program is loaded as a text file (<strong>program.