图灵机，作为自动机程序的模型
1.简介
编程需要新的通用算法模型，并且硬件不仅以不同的形式实现算法，而且还基于另一种算法模型-自动实现算法。 从硬件开发领域采用技术是自动化编程的关键思想。 但是，数字设备的合成与编程不同。 但是，一方面借用一个模型，不建议对其进行实质性的更改，但是另一方面，不能忽视现有的编程理论和实践。
接下来，我们将考虑用于设计自动化程序的SWITCH技术，您将在其中始终遇到这样的过程。 一方面，它极大地改变了状态机模型，从而使它实际上超出了自动机理论的范围。 另一方面，它引入了编程人员难以理解的编程概念，并且有时只是多余的，因为 在程序理论和编程实践中有更多熟悉的对应对象。
作为讨论自动编程问题的基础，我们采用了A. Shalyto最近的演讲 [1]及其关于“自动编程”范式定义的“编程”文章[2，3]。
1.自动化的对象，程序方案在讲座中，自动编程的成就是借鉴了自动控制理论（TAU），引入了自动控制对象的概念。 但是，回想一下，在TAU中，它们考虑的对象不是太多，而是系统，其中包括以下几个方面[4]：
基于此，谈论自动控制系统（ACS）会更正确。 现在让我们看一下图2所示的自行火炮的典型功能图。 1.如果将图灵机的磁带视为控制对象，则执行设备（IS）将成为实现磁带内容变化并移动磁头的MT元素，而测量设备（IS）将成为从磁带中读取信息的元素。
图1。 自行火炮功能图但是，如果有一种更接近计算机系统设计编程的实践，那么为什么要转向TAU，在这种实践中，当然包括MT的操作设备（OS）被视为操作（OA）和控制（UA）机器的组合。 而且，这更接近我们最终要努力实现的目标-证明自动编程的力量。 在图。 图2示出了Mayorov S.A.，Novikov G.I.的专着的文本屏幕。 电子计算机的结构[5]，其中详细讨论了运算放大器的设计问题。
图2。 管理器和操作机的概念但是，如果我们将计算机设计理论与程序理论进行比较，则可以在它们之间找到明显的结构类比。 在编程理论中，任何程序在结构级别上的模型都可以表示为程序方案S =（M，A，C），其中M是存储元素集，A是运算符集，C是控件[10]。 按照这种方法，任何图灵机程序也可以定义为一种程序方案，其中M组由带单元表示，操作员组由与1）单元分析，2）改变带单元中的字符和3）移动磁头相关的MT动作表示。
因此，程序方案的概念与所考虑的操作和控制自动机的概念完全相似，其中UA的模型是下面考虑的结构有限状态机（SKA）的模型，而OA“是对信息执行操作的结构”。 在这种情况下，OA包括数据存储元素（在内存之上）和用于处理信息的块，这些信息实现逻辑条件的计算和某些动作的实现（在许多运算符之上）。
从前述内容可以理解，磁带只能在条件上被认为是MT的控制对象。 仅由于图灵机的控制设备无法直接访问它，因为 所有与单元的操作都通过OA块间接实现。 另外，似乎不太熟悉，或者，如果不说，将其表示为程序（管理）的目标，作为控制系统，将代表存储器（磁带）的对象视为奇怪的事情。
因此，对于图灵机的正式定义，以及在它的上下文中有限状态机模型的地位，程序论的概念就足够了。 现在，与SWITCH技术框架中对自动机程序非常模糊的定义相反，我们可以说自动机程序是一种具有有限状态机模型形式的控制的程序。
程序本身是什么-具有简单或复杂的行为，具有逻辑控制，“具有显式状态分配”的“多样性”是什么，等等。 等 并不绝对重要。 最主要的是管理类型。 程序的其余元素可以在很宽的范围内确定-从最简单的图灵机到最复杂的任何形式的编程语言的运算符，函数和数据结构-汇编程序，高级语言等。
您还可以记得，图灵机长期以来一直被视为自动垫[6]，或者在极端情况下被认为是其简单的扩展[7]。 但是您需要了解它是什么类型的自动机，它是什么样的扩展以及它们是否等效于经典有限状态机的模型。 让我们尝试澄清一下。
2.在自动编程环境中进行图灵编程在图。 图3显示了专着[8]中MT增量函数的自动机。 从形式上讲，这显然不是MT程序，但已经不是经典的有限状态机。 在图。 图4显示了经典结构有限状态机（SKA）及其在VKPa环境（在Qt库和Qt Creator环境中使用C ++的可视组件自动编程环境）中的实现的图，该结构实现了相同的MT控制单元算法。
图3。 使用图灵机增加单位数量
图4 SKA形式的MT增量程序模型您会看到结构机器具有四个输入通道和五个输出通道。 这些通道中的每一个都与一个具有相同名称的程序功能相关联-谓词或动作。 在这里，谓词是没有参数的函数，这些函数根据正在查看的磁带单元的值返回布尔值，而动作是没有参数的函数，它们执行一个或另一个操作来更改磁带单元并移动图灵机的头部。
此SKA具有与图3中的自动机相同的状态集。 此外，除了SKA提供的自动机映射本身之外，它还实现了另外两个映射：将谓词集（x1，...，xM）映射到同一台机器的输入通道集，并将机器的输出通道集映射到许多相似的动作-y1，...，yN。 例如，如果当前单元格中存在1，则谓词x3将返回true（相同名称的输入信号的值为1），并且当机器的相同输出信号取值为1时触发的动作y4对应于将磁头向左移动（L），并且等 等
请注意，SKA并不直接控制磁带，而是执行[附加]映射，将自动机的信号与确定Turing机器许多操作的功能联系起来。 这再次使我们确信，在“老式”但数学上严格的映射概念已足够的情况下，无需引入自动控制对象的概念。
比较图中的自动机。 3和图。 如图4所示，可以看出SKA没有使用“ *”命令（见图1）。 在这种情况下，他不发出与该命令相关的信号就足够了。 另外，在相同转换处的两个或多个信号（输入和输出）是并行的。 因此，当访问共享对象有冲突时（例如，您需要更改单元格并移动磁头），将使用一种协议：对一个过渡的操作按其编号顺序依次执行。 在编号较小的动作之后执行编号较大的动作。 该协议不适用于谓词，因为 他们不更换磁带。 因此，我们使机器更紧凑，更直观（无需引入中间状态）。
在测试增量程序的过程中，确定了MT操作期间可能出现问题的情况。 首先，真正的磁带不是无限的，超出范围可能导致程序崩溃。 其次，有必要指出头部的初始位置。 如果没有此功能，例如，如果数字位于磁带的任意位置，并且磁头的初始状态位于数字的左侧且与空间相对，则磁头将立即开始向左移动。 然后它可能会超出磁带的边界，导致程序“崩溃”，或者向左移动了一步，它将写入单元格1，并挂起，将完成“成功”操作。 或者，如果该数字在所有位中都包含1，并且是从磁带的开头写入的，则将数字1转移到高位数字的最终尝试将导致相同的“崩溃”。
2.1。 C ++中MT的对象实现考虑在VKPa环境中使用C ++的图灵机的目标软件实现，该图实现了MT的任何程序，包括增量计算程序。
为此，创建了一个代表任何Turing机器的基类，该基类由实现一个或另一个MT程序的软件对象继承。 清单1中显示了这一基本步骤，清单2中显示了实现增量任务的程序。
清单1. MT基类的软件实现
#include "lfsaappl.h" class FTuringMashine : public LFsaAppl { public: FTuringMashine(string strNam, CVarFsaLibrary *pCVFL, LArc* pTBL); protected: int x15(); int x16(); void y14(); void y15(); void y16(); void y17(); QString strSrc;
清单2.图灵机的增量程序
#include "FTuringMashine.h" class FTIncrement : public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTIncrement(nameFsa, pCVarFsaLibrary); } FTIncrement(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); void y1(); void y2(); }; #include "FTIncrement.h" static LArc TBL_TIncrement[] = {
2.2。 使用C ++实现MT的程序示例考虑一个MT程序的示例，该程序“充当语言的接受者，即 它可以从[9]中识别语言。 其过渡函数如图2所示。 图5中的SKA形式的等效自动机。 6。
δ(1, a) = (2, x, R) δ(1, y) = (4, y, R) δ(2, a) = (2, a, R) δ(2, y) = (2, y, R) δ(2, b) = (3, y, L) δ(3, y) = (3, y, L) δ(3, a) = (3, a, R) δ(3, x) = (1, x, R) δ(4, y) = (4, a, R) δ(4, #) = (F, #, L)
图 5.图灵机的转换功能，可以识别语言{anbn：n≥1}
图 6.识别语言{anbn：n≥1}的图灵机的SKA图SKA形式的MT控制单元具有6个输入通道和7个输出通道。 接受程序还包括相应数量的谓词和动作，这些谓词和动作在自动机图右侧的图中显示。 清单3显示了VKPA环境中C ++程序的实现。
清单3.识别语言的图灵机程序{anbn：n≥1}
#include "FTuringMashine.h" extern LArc TBL_TAcceptor[]; class FTAcceptor : public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTAcceptor(nameFsa, pCVarFsaLibrary); } FTAcceptor(string strNam, CVarFsaLibrary *pCVFL, LArc* pTB = TBL_TAcceptor); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y18(); int nState{1}; friend class CDlgTAcceptor; }; #include "stdafx.h" #include "FTAcceptor.h" LArc TBL_TAcceptor[] = {
在清单3中，动作y18表示根据SWITCH技术方法的MT程序的变体。 在这种情况下，作为VKPA环境自动编程实现的一部分，代替了图1中的自动机。 在图6中，有必要实现具有一种状态的自动机，其在循环中发出信号y18。 它对应于清单3中转换表的注释掉的行。为了使自动机充当SWICH，您需要从该行中删除注释并注释掉其余行。
考虑来自[7]的图灵机程序的另一个示例，其中MT被定义为“有限状态机模型的非常简单的扩展”。 在这种情况下，用于图灵机的程序是过渡的部分定义函数的五分之一的有限列表，并输出δ：S×X→S×X×G。
MT程序找到两个数的最大公约数（GCD），如图2所示。 图7给出了与其等效的SKA图。 8.请注意，此处也未使用重写命令。 清单4显示了C ++实现。
图 7.图灵机的过渡图，该图计算两个数字的GCD，以及在处理一对数字<4，6>时的几种配置
图 8. SKA图，等效于图7中的图。 7清单4.图灵机的程序，用于查找两个数字的GCD
#include "FTuringMashine.h" class FTGrCmDiv: public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTGrCmDiv(nameFsa, pCVarFsaLibrary); } FTGrCmDiv(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y17(); }; #include "FTGrCmDiv.h" static LArc TBL_TGrCmDiv[] = {
总之，文章[11]中考虑了SWITH技术开发商的另一个MT程序，该程序提出了识别两个版本中括号的任务。 一种是麦莉机器的形式，另一种是混合机器的形式（分别在图9和图11中）。 对应于它们的结构自动机如图2所示。 10和图。 12.清单5显示了C ++程序的实现。
图 9.识别任意深度的括号。 英里换算图
图 10.识别任意深度的括号。 伯爵SKA Miles
图 11.识别任意深度的括号。 混合自动机的过渡图
图 12.识别任意深度的括号。 混合自动机过渡的SCA图清单5.用于识别括号的图灵机程序
#include "../FTuringMashine.h" class FTListing2 : public FTuringMashine { public: void MooreAction(); LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTListing2(nameFsa, pCVarFsaLibrary); } FTListing2(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y4(); void y5(); int i{0}; }; #include "FTListing2.h" static LArc TBL_TListing2[] = {
由于图中的自动机 12拒绝工作，决定去图中的机器。 图9显示了与之等效的SKA形式的自动机。 10.是的，从形式上来说，这也是一个混合自动机，从第一个实现中就留下了状态为“ 0”的信号和状态为“ 1”的信号y15（图12）。 在初始安装期间，第一个是必需的，并且y15信号实现了向右的头移，以读取下一个磁带字符。 SKA的其余部分对应于图1中的Miles机器。 9。
在图的自动机之后。 成功测试了10个，返回到图9中的机器。 11.显然，状态为“ 1”的信号z1_1是多余的（对于图12中的自动机，它是信号y2）。 问题在于，当他找到“左括号”时，他会将计数器增加两个单位，而当他找到“左括号”时，他根本不会改变它。 因此，当检测到“左括号”时，它将被调用两次-一次在标记为x2 / y2的循环中，第二次进入该状态。 并且当检测到“右括号”时，计数器首先在循环上减少，然后在进入状态时增加。
MT控件进行此工作的原因是作者对摩尔型自动机功能的错误解释。 显然，他们相信只有在进入摩尔状态自动机时才执行该信号（请参见从状态“ 0”到“ 1”的转换），但实际上，每次您进入该状态时都会发出该信号。 包括经过循环时。 因此，我们不是在处理错误（谁没有记错？），而是在处理更严重的问题-在摩尔型自动机功能的SWITH技术框架内的错误解释。 测试等效模型表明了这一点。
3.结论总而言之，我们可以说图灵和自动编程之间没有形式上的差异，因为 图灵机是自动机程序的抽象模型。 仅在后一种情况下，将使用更多的运算符和数据结构（内存）。 现在，我们可以放心地回答邮政机器作为普通程序模型与自动程序模型图灵机有何不同的问题。 管理模式，只有它，因为 其余的-内存和运算符可以相同。
因此，普通编程与自动编程的不同之处仅在于控制模型。 因此，尽管为了实现自动机而使用开关类型的普通控制操作员而不能使用类似的操作员，但严格来说，这种编程被认为是自动的。 这可能是自动机的模仿，但失去了其特定的特性，仅此而已。
因此，给出自动机程序和自动机程序设计的概念的定义，我们不必讨论“自动控制对象”，而只需要讨论具有经典有限状态机形式的控制的程序和程序。
我想提请注意的另一个有趣的事实。 在2000年代初，作者表达了他们对自动编程的理解，为广大读者所接受。 他们关于抽象机的文章发表在PC World杂志2002年第2期中[11，12，13]。 可以说，岁月并没有影响双方的信念。 虽然，也许这仅反映了他们对所选决策的信心程度。
例如，在“关于自动编程的新讲座”中，A。Shalyto 与之前的“带幻灯片的讲座”（十年前）相比，仅添加了基于“最新程序包” Stateflow的示例视频。 看来这证实了A. Shalyto观点的正确性，因为 Stateflow的开发者在UniMod中无法实现的功能（该项目似乎被“冻结”了）。 而且，可能是谁做的不是那么重要...
但是，在发布上述文章时，SWITCH技术的作者已经知道对此有所批评。 这不是秘密，因为 它可以在SoftCraft网站上找到[14]。 它还创建了专门针对自动编程的部分，特别是SWITH技术，尤其是KA技术。 在网站的论坛上讨论了作者的立场（当时该论坛是开放的）。 但是，所有人仍然不服气。
目前的结果如下。 曾经对SWITH技术表达的批评是相关和最新的。 它也适用于Stateflow程序包。 在SWITH技术中，没有自动编程，也没有明确的定义，自动机的实现方法没有改变，模型本身不是经典的，没有并行计算模型，等等。 等 在不消除这些问题的情况下，这种自动编程充其量只能发挥有限的作用。
上面提到的问题的原因很明显：尽管对自动机本身及其奇妙的特性说了许多好的和正确的话，但程序理论却被忽略了，自动机理论也被遗忘了。 但是实际上这些是其他机器。 作者深信创建原始模型的构思不当的可疑性。 它涉及同步，无功和其他模型。 当解决一小类问题时，它们很方便，仅此而已。 但是更严重的是，他们没有自己的理论就脱离了自动机理论。 但是理论之外的模型是无助的，因此实际上是毫无意义的。