模拟Turing机XN*2的运行过程

本文主要是介绍模拟Turing机XN*2的运行过程，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

模拟Turing机XN*2的运行过程

文件名称：模拟turing机XN*2的运行过程
编程语言：java
编译器：IntelliJ IDEA 2020.3.2 x64
完成日期：2021年4月10日

一、问题：

对于XN+1或XN*2图灵机进行模拟，任意给定的十进制数a，转换为收缩扩展二进制的编码，再编程模拟此Turing机的运行过程，要求输出从开始运行起的每一步骤的结果。

二、算法分析：

1、转换规则：将十进制数转换为二进制数并在末尾添上‘,’号，按照0->0、1->10、,->110的规则进行转换
2、图灵机的操作：XN*2图灵机，指令为0 0->0 0 R、0 1->1 0 R、1 0->0 1 R、1 1->11 0 R、10 0->11 1 R、11 0->0 1 STOP。

三、概要设计：

1、主要部分设计：
将整个程序共分为五个部分：首先从键盘接收一个十进制的整数；第二步将十进制数转换为二进制；然后按照转换规则将二进制数转换为二进制扩展码；接着根据图灵机XN*2指令对扩展二进制编码进行操作；最后再将扩展的二进制编码转换为二进制再转换为十进制，采用StringBuffer类型存储转化为二进制的字符串，利于后面的操作。
设计两个类：Main类和Turingmachine类。
Main类中主要进行数据的接收，通过建立Turingmachine类对象进行相关操作，并将结果输出，在输入数据的部分进行数据处理，防止出现不正确的输入，采用try-catch来捕获异常。

int n=0;
//进行数据处理，防止出现不正确的输入
while(true)
{Scanner scanner = new Scanner(System.in);try {n=scanner.nextInt();break;} catch (Exception e) {System.out.print("请重新输入:");continue;}
}

Turingmachine共设计了五个成员函数，分别为：change1()、change2()、turing()、change3()、ten()。
第一步就是输入十进制数并转换为二进制数，利用java内部提供的方法，直接进行api的调用。

//将十进制整数转化为二进制
public static String change1(int n) {String str = "";str+=Integer.toBinaryString(n);return str;
}

第二步即将二进制数转换为二进制扩展码，这里将字符串存入一个数组，利用for循环遍历数组，根据转换规则0->0、1->10、,->110，利用if判断，并将结果插入到字符串相应位置。

//将二进制数转化为扩展二进制  利用1->10,0->0,","->110规则进行转换
public void change2(int n, StringBuffer string) {int t = 0;     //记录string下一次插入的位置char A[] = string.toString().toCharArray();  //将字符串存入数组便于操作for (int i = 0; i < A.length; i++) {if (A[i] == '1') {t += 1;string.insert(i + t, "0");}}string.append("110");     //在末尾添上逗号
}

第三步便是主要步骤，这里利用turing()实现XN2指令对扩展二进制编码进行操作，实现XN2指令对扩展二进制编码进行操作，定义一个变量记录内态，同样将字符串存入数组以便于操作。利用for循环遍历数组，if进行判断内态和输入，根据指令0 0->0 0 R、0 1->1 0 R、1 0->0 1 R、1 1->11 0 R、10 0->11 1 R、11 0->0 1进行操作并输出每一步的转换结果。

//XN*2机制
public void turing(StringBuffer string) {String inter = "0";      //内态int t = 1;char[] A = string.toString().toCharArray();for (int i = 0; i <= A.length; i++) {if (inter == "0" && A[i] == '1') {inter = "1";string.setCharAt(i, '0');System.out.println("结果为:" + string + "从内态:0 输入:1变成内态:1 输出:0");t += 1;} else if (inter == "1" && A[i] == '0') {inter = "0";string.setCharAt(i, '1');System.out.println("结果为:" + string + "从内态:1 输入:0变成内态:0 输出:1");t += 1;} else if (inter == "1" && A[i] == '1') {inter = "10";string.setCharAt(i, '0');System.out.println("结果为:" + string + "从内态:1 输入:1变成内态:10 输出:0");t += 1;} else if (inter == "10" && A[i] == '0') {inter = "11";string.setCharAt(i, '1');System.out.println("结果为:" + string + "从内态:10 输入:0变成内态:11 输出:1");t += 1;} else if (inter == "11") {inter = "0";string.append("10");System.out.println("结果为:" + string + "从内态:11 输入:0变成内态:0 输出:1");t += 1;}}
}

接着将指令操作后的结果转换为普通的二进制数，利用1->10,0->0,”,”->110逆规则，将扩展二进制数转换为二进制，并且需要删除起始位置的0以及最后的110。

//将得到的扩展二进位数转换为二进制数，利用1->10,0->0,","->110的逆规则进行转换
public void change3(StringBuffer string) {string.deleteCharAt(0);           //删除扩展二进制初始位置的"0"string.delete(string.length() - 4, string.length() - 1); //删除扩展二进制后的逗号 ”110“char A[] = string.toString().toCharArray();int t= 0;for (int i = 0; i < A.length; i++) {if (A[i]=='1' && A[i+1]=='0') {string.deleteCharAt(i+1-t);t+=1;i+=1;}}
}

最后将得到的二进制数转换成十进制并输出，同样利用java内部提供的方法，直接进行api的调用。

//将结果转换为十进制public void ten(StringBuffer string) {int m=Integer.valueOf(string.toString(),2);System.out.println("最后的结果为："+m);}
}

2、流程图：

四、调试

1、调试十进制转换成二进制部分：
在这里插入图片描述

2、调试转换为二进制扩展码部分：

3、调试XN*2指令操作：

4、调试扩展二进制数转换为二进制部分：

5、调试二进制的结果转换成十进制部分：

五、结果展示

六、总结

在本次程序设计实现过程中，遇到了以下几个问题：首先是关于进制的转换，刚开始是利用之前在c++中学过的方法进行转换，后来发现这样过于繁琐，查询资料后发现可利用java内部提供的方法，直接进行api的调用，大大提高了效率。其次是对于二进制扩展码以及XN2机制的操作，起初对于字符串中每个字符的操作比较迷糊，后来想到利用toString()、toCharArray()函数将字符串存入一个数组，利用for循环遍历数组完成相关操作。通过此次程序设计更加加深了对于图灵机XN2操作的理解，熟悉了每一步的指令操作，也提高了对java中相关函数使用的熟练度。如有错误也欢迎大家进行指正。
最后附上本次程序的完整版代码：

/*** @author wangym* @create 2021-04-09 21:25*/
public class Turingmachine {//将十进制整数转化为二进制public static String change1(int n) {String str = "";str+=Integer.toBinaryString(n);return str;}//将二进制数转化为扩展二进制  利用1->10,0->0,","->110规则进行转换public void change2(int n, StringBuffer string) {int t = 0;     //记录string下一次插入的位置char A[] = string.toString().toCharArray();  //将字符串存入数组便于操作for (int i = 0; i < A.length; i++) {if (A[i] == '1') {t += 1;string.insert(i + t, "0");}}string.append("110");     //在末尾添上逗号}//XN*2机制public void turing(StringBuffer string) {String inter = "0";      //内态int t = 1;char[] A = string.toString().toCharArray();for (int i = 0; i <= A.length; i++) {if (inter == "0" && A[i] == '1') {inter = "1";string.setCharAt(i, '0');System.out.println("结果为:" + string + "从内态:0 输入:1变成内态:1 输出:0");t += 1;} else if (inter == "1" && A[i] == '0') {inter = "0";string.setCharAt(i, '1');System.out.println("结果为:" + string + "从内态:1 输入:0变成内态:0 输出:1");t += 1;} else if (inter == "1" && A[i] == '1') {inter = "10";string.setCharAt(i, '0');System.out.println("结果为:" + string + "从内态:1 输入:1变成内态:10 输出:0");t += 1;} else if (inter == "10" && A[i] == '0') {inter = "11";string.setCharAt(i, '1');System.out.println("结果为:" + string + "从内态:10 输入:0变成内态:11 输出:1");t += 1;} else if (inter == "11") {inter = "0";string.append("10");System.out.println("结果为:" + string + "从内态:11 输入:0变成内态:0 输出:1");t += 1;}}}//将得到的扩展二进位数转换为二进制数，利用1->10,0->0,","->110的逆规则进行转换public void change3(StringBuffer string) {string.deleteCharAt(0);           //删除扩展二进制初始位置的"0"string.delete(string.length() - 4, string.length() - 1); //删除扩展二进制后的逗号 ”110“char A[] = string.toString().toCharArray();int t= 0;for (int i = 0; i < A.length; i++) {if (A[i]=='1' && A[i+1]=='0') {string.deleteCharAt(i+1-t);t+=1;i+=1;}}}//将结果转换为十进制public void ten(StringBuffer string) {int m=Integer.valueOf(string.toString(),2);System.out.println("最后的结果为："+m);}
}import java.util.Scanner;
/*** @author wangym* @create 2021-04-09 17:37*/
public class Main {public static void main(String[] args) {Turingmachine turingmachine=new Turingmachine();StringBuffer string=new StringBuffer();System.out.println("请输入一个整数:");int n=0;//进行数据处理，防止出现不正确的输入while(true){Scanner scanner = new Scanner(System.in);try {n=scanner.nextInt();break;} catch (Exception e) {System.out.print("请重新输入:");continue;}}turingmachine.change1(n);System.out.println("转换后的二进制数为："+turingmachine.change1(n));string.append(turingmachine.change1(n));turingmachine.change2(n,string);   //将二进制数转换为扩展二进制System.out.println("转换后的扩展二进制为:"+string);System.out.println("下面开始进行图灵机XN*2操作");turingmachine.turing(string);  //进行XN*2操作turingmachine.change3(string);    //将扩展二进制还原为二进制System.out.println("所得数的二进制数为："+string);turingmachine.ten(string);}
}