TMD-2:图灵机演示器标记2

5,342

15

6

简介:TMD-2:图灵机演示器Mark 2

关于:帮助我们保存一小部分非数字化的过去。

这是我的一个后续指令TMD-1:图灵机演示器项目。

我真的很高兴TMD-1的结果。我相信我成功地创建了一个图灵机器,它既“易于编程”又“易于理解”。为了帮助实现这些目标,机器本身仅限于3个状态、3个符号和一个10个单元的小磁带。出于教育目的,这很好,但如果你想更深入地探索图灵机器,就有点贫乏了。

对于这个项目,我想“提高赌注”。我做了一个6状态,6符号的机器,有很大的磁带容量。我尽量从TMD-1中提出简单易用、易懂的原则。

在本教程中,我将重点介绍构建TMD-2所需的步骤。不过,我认为有时需要一些背景知识来为构建提供上下文,比如现在。

什么是图灵机器?

图灵机器是由艾伦·图灵于1936年发明的。通过对能够进行任意计算的简单装置进行数学描述,他能够证明计算的一般性质。

图灵机器在数学上模拟了在磁带上运行的机械机器。更明确地说,图灵机包括:

  • 分成相邻单元的带子。每个单元包含一个来自有限字母表的符号。字母表包含一个特殊的空白符号和一个或多个其他符号。假设以前没有写入的单元用空白符号填充。
  • 一种磁头,可以读写磁带上的符号,一次只能在磁带上左右移动一个单元。
  • 一种状态寄存器,用于存储图灵机的状态,图灵机是许多图灵机之一。其中包括初始化状态寄存器的特殊启动状态。
  • 一种有限的指令表,给定机器当前的状态和它在磁带上读取的符号(当前在磁头下的符号),它告诉机器按顺序执行以下转换步骤:
    1. 从有限的字母表中写一个符号来代替原来的那个。请注意,所写的符号可能与之前相同或不同。
    2. 将头部向左或向右移动一个单元格。
    3. 假设与“去往州”规定的相同或新的州。

TMD-2型

图灵机演示器标记2(TMD-2)将具有以下特性:

  • 一个有100000个细胞和一个磁头的带子。
  • 使用的字母表将有七个符号:{0,1,2, 3, 4, 5,b类}.0将是空白符号和b类是可以从磁带中读取但不能写入的结束标记符号。
  • 将有六个州:{A,B类,C、 D、E、F}.A将是开始状态加上有一个特殊的停止状态小时.

使用TMD-2,您可以执行以下任务:

  • 把输入区域当作一个二进制数来寻找对方的赞美。
  • 在输入区域中找到二者对“二进制”数的补充。
  • 二进制计数(升序和降序)。
  • 分类。将输入区域中的所有1向左或向右移动。
  • 将输入区域向右或向左移动一个单元格。
  • 运行“忙碌的海狸”计划多达六个州。

附加信息

  • 如果你对图灵机器的更多细节感兴趣维基百科条目非常好。
  • 特别是关于TMD-2的背景资料,我有一个Hackday博客在那里,我记述了我的旅程,构思和建立图灵机演示马克2。
  • 我还写了一本小册子,TMD-2快速入门指南。它描述了TMD-2的操作,并帮助用户运行他们的第一个“程序”。你会发现这本书所附的指南是可以指导的。

好 啊。我们来造一架TMD-2。

用品:

除了您可能需要的打印部件外:

第1步:决定你想要制造多少TMD-2

TMD-2的核心是一个用Python编写的独立程序。如果您只想尝试这个应用程序,它将运行在任何支持Python的计算机(这是大多数机器)上,请跳到安装TMD-2软件开始步骤。

我建立了我的TMD-2使用树莓皮与树莓皮7“触摸屏显示作为我的电脑。一个展示架被设计用来放置这些部件,并成为我整个项目的控制台。你可以用TMD-2软件加载“console”,然后停在那里。这种配置使一个很好的“桌面玩具”图灵机。我在配置中添加了无线鼠标和键盘,但它们不是必需的。

要获得全面的TMD-2体验,您可能需要构建有限状态机输入面板。然后,您可以通过使用3D打印的“瓷砖”填充此转换表来编程图灵机器。使用Raspberry Pi摄像头模块,通过OCR软件处理摄像头的图像,将这些瓷砖“扫描”到机器中。

你想要多少TMD-2?

第二步:打印零件

根据所选的TMD-2配置,您可能正在打印此处列出的部分或全部零件。我使用以下设置打印部件(除非另有规定):

打印分辨率:0.2毫米

填充:20%

长丝:AMZ3D PLA公司

笔记:没有支持。以默认方向打印零件。

要制作TMD-2,您需要打印以下部分:

  • 1-树莓皮显示器支架
  • 4-显示锁定选项卡
  • 10-平铺0注:把所有的瓷砖都印成白色。在6.2毫米处暂停打印并切换到黑色。
  • 10-瓷砖1
  • 10-瓷砖2
  • 10-瓷砖3
  • 10-瓷砖4
  • 10-瓷砖5
  • 10-瓷砖b
  • 10-瓷砖L
  • 10-瓷砖R
  • 10-瓷砖A
  • 10-平铺大B
  • 10-瓷砖C
  • 10-瓷砖D
  • 10-瓷砖E
  • 10-瓷砖F
  • 10-瓷砖H
  • 1-状态转换表注:将所有表格打印为白色。在4.2毫米处暂停打印
  • 1-B状态转换表并切换到黑色。
  • 1-C状态转换表
  • 1-D状态转换表
  • 1-状态转换表
  • 1-F状态转换表
  • 1-州标签
  • 1-瓷砖箱底座注:如果您想为您的瓷砖制作一个箱子,请只打印以下内容。
  • 1-平铺箱底部左侧注:如果上面的底边太大,只打印左右底边。
  • 1-右侧平铺箱底座
  • 15-瓦片箱
  • 1-平铺箱标签注:用白色打印。在1.2毫米标记处暂停打印并切换到黑色。

附件

步骤3:组装控制台

这一步真的不多。按照显示器附带的说明将覆盆子圆周率贴在显示器背面,也可以找到在这里.

将显示器置于Raspberry Pi显示器支架的背面,并用显示器锁片固定到位,如上图所示。

步骤4:组装有限状态机面板

有限状态机的一点背景知识。

有限状态机

图灵机的核心是有限状态机,一组有限的指令,给定机器当前的状态和它在磁带上读取的符号(当前在磁头下的符号),告诉机器如何转换到下一个计算状态。这些有限状态机通常用两种方式之一来描述。作为状态转换图:

或作为状态转换表:

对于这个构建,输入将使用状态转换表来完成。这就是TMD-2的输入区域:

上表中的空白框将具有浅矩形凹陷,可在其中设置适当标记的“瓷砖”:0/1/2/3/4/5/b表示写入,L/R表示移动,A/b/C/D/E/F/H表示转到。TMD-2将能够“读取”这些瓦片以确定状态机的定义。我把这个叫做我的“Azul”界面,是基于流行的基于瓷砖的棋盘游戏的名字。

装配

首先打印六个状态转换表“卡片”,每个状态(A、B、C、D、E、F)有一个矩形凹口。

下一步,建立一个基地,以举行国家“卡”和图例与标签为每一行。使用3 1/2“x 3/4”木材作为框架。使用1/2“x 1/2”为1/8”的胶合板创建一个“壁架”。

这里两个重要的事情是胶合板件应该坐在大约1/8“以下的框架顶部,应该是14 1/3”x 8 57/64“(364毫米x 224毫米)的大小,以确保卡和图例适合紧密。

一点白色油漆加上印刷状态转换表件的增加看起来像这样。

我发现了一个关节臂设计由克里斯罗杰斯(哈克霍利克)在Thingiverse公司. 他的动作捕捉装置和我建造的底座非常相似,所以非常适合。按照克里斯的“东西”做手臂。臂安装在状态转换表盒的背面,以表本身为中心(B上方)。

Raspberry Pi摄像机紧贴地卡入摄像机支架,带状电缆通过导轨轻松滑动。很棒的设计!

按照相机附带或找到的说明,将有限状态机面板的相机与控制台的Raspberry Pi连接起来在这里.

硬件就是这样。

步骤5:安装TMD-2软件

要求

运行基本TMD-2应用程序只有两个先决条件。

  1. python3必须安装到目标计算机上。
  2. PyGame模块必须加载到Python环境中。

如何做到这一点将取决于您使用的操作系统。这里有一个关于如何安装python3在各种环境中。类似地,这里有一个链接安装PyGame进入同样的环境。

安装TMD-2

  1. 转到图灵机器演示器Mark 2发布github页面。
  2. 下载最新版本的源代码存档,可以是.zip或焦油.gz文件。
  3. 将检索到的存档文件解压缩到您选择的文件夹中。

运行TMD-2

  1. 打开命令提示符。
  2. 导航到源代码扩展到的文件夹。
  3. 运行命令:蟒蛇3 Tmd2控制台.py

您将看到以下窗口打开:

学习TMD-2

随着应用程序的运行,我强烈建议您通过TMD-2快速入门指南附属于这个指令的。第一部分将告诉您TMD-2应用程序是如何工作的,接下来的练习将教您图灵机器是如何工作的。最后,对于那些想学习更多的人来说,还有一些额外的挑战。

自动启动TMD-2

如果你像我一样在Raspberry-Pi上运行TMD-2作为一个专用控制台,那么当机器启动时,让程序自动启动是很方便的。这就是我所做的一切。

我创建了一个自动启动文件夹并切换到该文件夹。

mkdir/home/pi/.config/autostart cd/home/pi/.config/autostart目录

在刚刚创建的autostart文件夹中,我添加了以下两个文件。

运行TMD2

cd/home/pi/Apps/Tmd2控制台/usr/bin/python3 Tmd2控制台.py

TMD-2.桌面

[桌面输入]Type=Application Name=TMD-2 Exec=/home/pi/.config/autostart/runTmd2

此外,必须使用以下命令使runTmd2文件可执行:

chmod-x运行tmd2

如果您重新启动系统,您应该会看到桌面出现,不久后TMD-2应用程序将加载。

步骤6:安装摄像头和OCR软件

如果要使用有限状态机输入面板,则需要安装一些附加软件。这些说明仅适用于Raspberry Pi Raspbian操作系统。

摄像机软件

因为我们是从Python环境访问Pi摄像机,所以我们需要安装picamera库。Picamera已经是我的Raspbian发行版的一部分了。如果它不在您的Raspberry Pi运行的命令行中:

$sudo apt get更新$sudo apt get安装python picamera python3 picamera

OCR软件

TMD-2使用Tesseract OCR库。要使用OCR,必须安装几个软件包,即:

  • tesseract光符识别
  • 藏书台开发
  • 脓肿
  • 打开CV

教程基于OpenCV和Tesseract的树莓Pi光学字符识别描述如何安装这些软件包。

步骤7:运行TMD-2状态转换表扫描程序

正如通过github交付的一样,TMD-2应用程序被配置为在没有摄像头的情况下以独立模式运行。要启用相机和扫描状态转换表面板的功能,请编辑Tmd2控制台.py将第4行从hasCamera=错误hasCamera=真.

启动Tmd2时控制台.py同样,您应该看到上图中的屏幕。你会注意到一些不同之处。首先,应用程序是全屏的,意味着要填补所有的树莓Pi显示没有任何“窗口”控件。另一个区别是新的扫描按钮。如果单击“扫描”,将出现以下全屏对话框。

屏幕显示由Raspberry Pi相机拍摄的状态转换表面板的静态图像。如果需要调整铰接臂以获得与上述视图类似的视图,请单击“刷新”按钮以启用图像的连续更新,以便进行调整。如果您满意图像包含整个表格(左侧的标签无关紧要),并且表格边缘与图像边框相对垂直(即表格不应偏离矩形太多),请再次单击“刷新”以停止连续更新。

用紫色的“橡皮筋”勾勒出桌子的轮廓。设置完轮廓后,单击“开始”按钮扫描平铺。这是一段拍摄过程的视频。

注意,在这个例子中,tile并不代表一个真正的图灵程序,它们只是出于演示和测试的目的。您只需在第一次使用SCAN时执行此“设置”。随后的扫描将更新照片并记住轮廓设置,因此您只需单击“开始”。

第八步:做些瓷砖

如果您使用的是状态转换表面板,您将需要一堆瓷砖。我先印了10张。瓷砖应以白色印刷,并带有黑色符号,以获得最佳OCR结果。

我已经包括了STL文件的一个简单的零件盒在这个指令,但任何便宜的零件组织者当然会做。

第九步:最后的想法

设计和建造TMD-2对我来说是一次非常“舒展”的经历。在硬件方面,我从来没有广泛使用过树莓Pi或Pi相机。在软件方面,我以前从未使用过Python或PyGame。所以我学会了很多把TMD-2放在一起。

Python是一种很棒的语言,但它需要一点时间来适应。我基本上是Java背景,所以放弃使用{}作为块分隔符感觉很不自然。即使在使用Python几个月之后,我仍然发现自己想在行的末尾放一个。我从来没有掌握在变量名中使用u2;的窍门,所以一直坚持使用camelCase。但那只是我。Python当然符合它的跨平台名称。控制台应用程序的开发在Windows/Eclipse开发环境和Raspbian目标环境之间平稳地进行。当我开始集成相机并切换到Pi进行所有开发时,我发现我可以很容易地使用笔记本电脑上的RealVNC在Pi上进行开发,这给了我更多的屏幕空间,因为我在Pi上的唯一显示是7英寸的触摸屏。

PyGame是推荐给我的,我很高兴我选择它作为控制台的框架。我唯一错过的就是一些GUI模块。我尝试集成了许多推荐的外部库,但最终还是在PyGame中创建了自己的对话框。这样做的缺点是,我的实现有点轻功能,但另一方面,它们保持了整个应用程序的美观。

这个项目的软件开发比我想象的要多。刚开始的时候,我认为TMD-2是TMD-1的硬件继承者。我将构建硬件并为控制台编写一个小程序。在编写控制台的过程中,我意识到我所做的将是一个非常好的独立应用程序。我添加了一些特性,这样程序就可以在没有基于摄像头的输入的情况下运行,主要是允许通过鼠标单击来编辑状态表。由于Python是跨平台的,它几乎可以在任何地方运行。最后,我把TMD-2看作是一个图灵机程序,它从TMD-1中获得了易用性和易于编程的概念,并使它们能够被更广泛的受众所接受。TMD-2还支持一个很酷的可选的基于tile的接口来定义状态转换表。

我想随着TMD-2的完成,我已经有一段时间没有图灵机器了。继续下一个项目。

我给你留一段TMD-2在演示模式下运行一个3状态2符号“busy beaver”程序的视频。

第一个分享

    建议

    • 让它发光比赛

      让它发光比赛
    • 第一次作家大赛

      第一次作家大赛
    • PCB挑战

      PCB挑战

    6讨论

    你应该参加“一切顺利”比赛。这肯定是个大奖得主。

    0
    梅加迪

    10天前回复

    谢谢!我希望我能,但这不符合条件。我希望我目前的项目将及时完成,但进入。

    0
    休斯谁

    12天前

    做得好。令人印象深刻的项目!

    0
    梅加迪

    12天前回复

    非常感谢。我也喜欢你一直在做的工作。

    这是惊人的,所以很好的记录!感谢您分享.stl文件并解释您的过程。:)

    0
    梅加迪

    14天前回复

    非常感谢。我感谢你的好话和支持。