搜索
典型图灵机的Java编程示例一图灵机概述图灵机(TM)是一种重要的计算模型，它由英国数学家A．M．Turing于1936年提出。这个模型很好的描述了计算过程。无数的事实表明，任何算法都可以用一个图灵机来描述，这就是著名的丘奇论题。图灵机在可计算性理论中起着重要作用。可以证明图灵机识别的语言就是0型语言。图灵机的组成如下图所示：它由一个状态控制器，一个读写头和一个输入带组成。其中输入带左右端可以无限伸长。带上的每一格恰好有一个字符。开始时，带上从编号为0开始的n个格存放着由有限输入字母表上的字符组成的字符串，第0格及其左边和第n＋1格及其右边各格均为空白。空白是一个特殊的带符号，它不属于输入字母表。读写头一次可以在带上读或写一个字符，并可根据指令向左或向右移一格。状态控制器根据当前的状态，读到输入字符并发布指令。指令的内容包括状态转换，在带上的一格写上(更换)字符，以及读写头向左或向右移动一格等。带子上的无穷多个小格可写、可擦；读写头可沿带子左右移动并在带上读写；每个图灵机有一个状态集Q，其中有一个开始状态和一个结束状态；还有一个符号集Σ={0,1，*}；可形式化地描述为：图灵机是一个七元组M=(Q,T,Σ,δ,q0,B,H)其中:Q---有限的状态集合;Σ---有限的带字符集合;B---空白符号,B∈Σ;T---输入字符集合,T⊆Σ且B∉T;δ---下一次动作函数,是从QxΣ到QxΣx{L,R}的映射，即控制器的规则集合q0---初始状态,q0∈Q;H---终止状态集合,H⊆Q.工作过程：首先从开始状态启动，每次动作都由控制器根据图灵机所处的当前状态和读写头所对准的符号决定下一步动作（或称操作）其中每一步包含三件事。各符号写到读写头当前对准的那个小格内，取代原来的符号。读写头向左或向右转动一格、或不动。一次动作会引起:(1)控制器改变状态;(2)在当前扫描到的单元上,重写一个字符取代原来的字符;(3)读写头左移或右移一个单元;根据控制器的命令用某个状态（可以是原状态）取代当前的状态，使用图灵机进入一个新的状态。控制器的命令：（状态、符号）→（写符号，移动、状态），当图灵机进入一个结束状态就停机。计算任务宣告完成，带上的内容即为输出结果。二图灵机模拟器编程1软件开发环境简介（1）JavaJDK——Java开发的底层支持工具（2）Eclipse3.2——Java开发的IDE工具，用于编写图灵机的功能实现类和调用界面2图灵机概要设计首先以下面的例子剖析一下设计图灵机的算法思想2.1含有同等数量a和b的字符串识别器分析:最初,图灵机M的带上已有字符a..b..a,前后都跟无限多个空白符#,如下图(a),M开始动作的第一步先读到最左边的第一个a(或b),并改写为X,如下图(b).然后右移去读最左边的第一个b(或a),并改写为X,如下图(c).又左移当发现最边的X时,再看紧接着X之后是否为a(或b),若为a(或b),将其改写为X,然后再右移找X,若紧接X之后是b(或a),又将其改写为X.如此反复进行.图灵机M按以上反复动作过程中,会出现以下情况:(1)当找a（b）时,如果不再有a(b),M应转向找b(a),如果还能找到b(a),说明b(a)的个数多于a(b)的个数,则M停止,表示不接受.如果找不到b(a),说明a(b)与b(a)的个数相同,M应该进入终止状态.表示接受.(2)当找b(a)时,出现空白符#,说明a(b)的个数多于b(a)的个数,M停止,不接受.通过上面的分析,可构造图灵机M=(Q,T,Σ,δ,q0,#,F)，其中:Q={q0,q1,q2,q3,q4}T={a,b}Σ={a,b,X,#};F={q4}δ函数定义如下:δ(q0,a)=(q1,X,R)δ(q2,a)=(q2,a,L)δ(q0,X)=(q3,X,R)δ(q2,X)=(q0,X,R)δ(q1,a)=(q1,a,R)δ(q2,X)=(q2,X,L)δ(q1,b)=(q2,X,L)δ(q3,X)=(q3,X,R)δ(q1,X)=(q1,X,R)δ(q3,#)=(q4,#,R)当M接受句子aabb时,其动作过程用格局表示为:q0aabb┠Xq1abb所使用的函数δ(q0,a)=(q1,X,R)┠Xaq1bb所使用的函数δ(q1,a)=(q1,a,R)┠Xq2aJb所使用的函数δ(q1,b)=(q2,X,L)┠q2XaXb所使用的函数δ(q2,a)=(q2,a,L)┠Xq0aXb所使用的函数δ(q2,X)=(q0,X,R)┠XXq1Xb所使用的函数δ(q0,a)=(q1,X,R)┠XXXq1b所使用的函数δ(q1,X)=(q1,X,R)┠XXq2XX所使用的函数δ(q1,b)=(q2,X,L)┠Xq2XXX所使用的函数δ(q2,X)=(q2,X,L)┠XXq0XX所使用的函数δ(q2,X)=(q0,X,R)┠XXXq3X所使用的函数δ(q0,X)=(q3,X,R)┠XXXXq3所使用的函数δ(q3,X)=(q3,X,R)┠XXXXq4所使用的函数δ(q3,#)=(q4,#,R)进一步，在设计过程中如何将已规划好的函数及格局等体现在图灵机执行过程中，用下面的例2说明。2.2用于计算“x+1”的图灵机。我们根据图灵机的原理，利用二进制来设计一个专门计算“x+1”的图灵机，要求计算完成时读写头要回归原位。于是我们设计的图灵机为：状态集合Q:{start,add,carry,noncarry,overflow,return,halt}字母表∑：{0,1,*}初始状态q0：start停机状态H：halt规则集合δ：（见表2.1）输入响应当前状态当前符号新符号读写头移动新状态StartAddAddAddCarryCarryCarryNoncarryNoncarryNoncarryOverflowReturnReturnReturn*01*01*01*0或101**10*10101**01*leftleftleftrightleftleftleftleftleftrightrightrightrightstayAddNoncarrycarryhaltnoncarrycarryoverfloenoncarrynoncarryrightrightrightrighthalt有了以上这些假设，我们来看该图灵机是如何具体进行计算动作的：假定x=5，则图灵机的初始状态如图2.2所示，箭头表示读写头当前的位置。再从规则表2.1可知，当前状态为“add”,当前符号为“1”时，读写头的响应为：改写当前符号为“0”，并向左移动一格，内部状态改变为“carry”表示有进位，如图2.4所示：接下来从规则表2.1可知，读写头应改写当前符号为“1”，并向左移动一格，进入“noncarry”状态，表明没有进位，如图2.5所示：此时，从规则表2.1知道：读写头不改写当前符号，只是继续向左移动一格，指向“*”,如图2.6所示：这时实际已经完成“5＋1＝6”的计算，因为我们要求读写头要回归原位，按规则接下来就是将读写头一路右移直到原位“*”,内部状态保持为“return”状态，如图2.7所示：从读写头状态可知，图灵机这时还处在运行状态，从规则表中可知，当读写头状态为“return”且当前符号为“*”时，则应进入“halt”状态，由于“halt”状态是该图灵机的停机状态，所以，图灵机停止运行，圆满地完成了计算要求，如图2.8所示：有了上面设计算法思想的铺垫，下面给出本次开发的某一特定功能图灵机的工作过程示意。图灵机模拟器编程示例：2.3一元至二元的转换功能：将输入的字母的个数转换成二进制数目前状态和输入，用黄色高亮显示。我们追踪其执行。扫描到当前输入是A，图灵机根据状态转移箭头匹配：A：X，图灵机将当前输入A改写为X。带头从此位置左移一个位置，到达下一个状态（新的状态标识为L左移）。下图为其上描述的第一步。当前单元格内容为：＃，图灵机根据状态转移箭头匹配：#：1，图灵机将当前#改写为1，带头从此位置右移一个位置，到达下一个状态（新的状态标识为R右移）。下图是接下来的几个步骤示意图：循环直至所有的输入都被改写覆盖为X，图灵机除去所有的X（即用#覆盖），并到停机状态。灵机上文所述的转换，从一元至二元。即如果输入构成的N一连续的，那么图灵机打印数N在二元到左边的序列一的（和覆盖一的与X的）。在上面的例子中，输入由6个字母A组成的串，图灵机将其改写为二进制数110到输入带上。执行节结果图如下：3图灵机功能实现程序结构剖析(八种常用图灵机模型示例)3.1二进数加法BinaryAdder：binaryadder.tur，模型如下图：3.2二进制计数器BinaryCounter：binarycounter.tur，模型图如下：3.3二元回文BinaryPalindromeDecider：binarypalin.tur，模型图如下：3.4同等数量a和b的识别器EqualNumberofa'sandb's：equalab.tur，模型图如下：3.53的倍数识别器Multipleof3Decider3：mult3.tur，模型图如下：3.6括号匹配器ParenthesisMatcher：paren.tur，模型图如下：3.7含有偶数个a的字符串识别器ParityDecider：parity.tur，模型图如下：3.8一元至二元转换器Unary-to-BinaryConverter：unarytobinary.tur，第二部分2.3中已分析过其功能，模型图如下：4图灵机执行代码结构剖析每一个主要图灵机组件（输入带，转换，控制状态）使用良好的面向对象的原则。输入带，Tape.java（类方法结构图如上左）是代表无界图灵机的输入带。它支持下列功能：左移，右移带头，读取当前单元格中的字符，改写当前单元格的内容。为实现上述功能，使用两个栈（一是存储所有左移的符号，二是存储所有右移的符号）。为显示输入带内容，首先将第一个栈中内容的逆向并将其显示，其次是当前元素，最后是第二个栈的内容。状态，Vertex.java（类方法结构图如上右）：一个点代表图灵机的一个状态。变量“name”是用于唯一标识状态的字符串，每个状态有一个名字和类型；“haltStatus”可以取五种值（左移，右移，停机，接受，或拒绝），标识带在进入一个状态时的移动方向，或标识停机状态。“xpos”和“ypos”有0和1.0两者取值，用于标识图灵机图形化界面中点的中心位置（用高和宽即横纵坐标一起标识，（0，0）表示处在屏幕界面的左上方，（1.0，1.0）表示在右下方）。Ege,java（类方法结构图如上左）：包含图灵机图形的边的信息。在图形化用户界面中，一条边是连接两个点的一条线，本程序中它代表两个状态之间的转换，转换条件会触发该次转换。如果当前处于旧状态，带上同步标识旧标识，当前状态将转移至新状态并将新标识改写至当前带位置。变量“curve”取值在-1.0和1.0之间，用于标识边的弯曲率，若取0，即边为一直线；取-1.0和1.0时，边都为一半圆弧线，正值时，边为逆时针方向从旧状态指向新状态，负值时，边为顺时针方向从新状态指向旧状态。TuringIOProcessor.Java（类方法结构图如上右）：图灵机工作过程中读带时用到的一组方法的类Machine.Java（类方法结构图如上左）：用于存储图灵机当前状态轨迹的类TuringMachineArea.java（类方法结构图如上右）：将图灵机以图形化的形式显示出来，即描绘整个图灵机的图形化用户界面。TuringMain.java（类方法结构图如上左）：用于图形化界面中组件、事件的协调驱动。TuringTapeArea.java（类方法结构图如上右）：描绘和控制带的显示。TuringMachine.Java：包含主函数的Java应用程序，主要显示图形化界面的外框。三总结与体会1图灵机小结图灵机实质上抽象出了我们平素进行机械式计算的核心规律，可形象的理解为“一个人+纸笔+一定的规则”进行机械运算。这么个理论机器首