|
对于任意给定的一台Turing机和任意给定的字符串w(w不含空格)，编程模拟此Turing机的运行过程，要求输出从开始运行起的每一步骤的结果。
1. 掌握图灵机的概念和基本结构，理解图灵机的基本指令和编码方式；
2.掌握图灵机的编程方法；
程序框图
图灵机XN*2在扩展二进位上实现运算指令为：
0 0->0 0 R 0 1->1 0 R 1 0->0 1 R
1 1->10 0 R 10 0->11 1 R 11 0->0 1 STOP
算法设计：
建立一个TL类，在其中定义panduan()函数。在panduan()函数中定义数组shuru[],依次在键盘上输入数据，将初始内态设为0。利用if-else if 语句根据运算指令判断内态和输出的变化，每次循环用continue语句，结束本次循环，进入下一个循环，最后一个指令用break语句，结束循环输出结果。
源代码
#include <iostream>
using namespace std;
class TL//建立一个TL类
{
public:
int panduan();
};
int TL::panduan()//判断函数 panduan()
{
int n;
int shuru[11];
int neitai=0;
cout<<"请输入拓展二进位编码："<<endl;
for(int s=0;s<11;s++)//将输入拓展二进位编码设置为11位数
{
cin>>shuru[s];
}
for (int i=0;i<11;i++)
{
if (shuru[i]==0 && neitai==0)//00->00
{
shuru[i]=0;
neitai=0;
cout<<"内态变为0，输出变为0。输出为：";
for(int j=0;j<11;j++)
{
cout<<shuru[j];
}
cout<<endl;
continue;//跳出本次循环，进行下一次循环
}
else if (shuru[i]==1 && neitai==0)//01->10
{
shuru[i]=0;
neitai=1;
cout<<"内态变为1，输出变为0。输出为：";
for(int j=0;j<11;j++)
{
cout<<shuru[j];
}
cout<<endl;
continue;
}
else if (shuru[i]==0 && neitai==1)//10->01
{
shuru[i]=1;
neitai=0;
cout<<"内态变为0，输出变为1。输出为：";
for(int j=0;j<11;j++)
{
cout<<shuru[j];
}
cout<<endl;
continue;
}
else if (shuru[i]==1 && neitai==1)//11->10 0
{
shuru[i]=0;
neitai=10;
cout<<"内态变为10，输出变为0。输出为：";
for(int j=0;j<11;j++)
{
cout<<shuru[j];
}
cout<<endl;
continue;
}
else if (shuru[i]==0 && neitai==10)//10 0->11 1
{
shuru[i]=1;
neitai=11;
cout<<"内态变为11，输出变为1。输出为：";
for(int j=0;j<11;j++)
{
cout<<shuru[j];
}
cout<<endl;
continue;
}
else if (shuru[i]==0 && neitai==11)//11 0->0 1 stop
{
shuru[i]=1;
neitai=0;
cout<<"内态变为0，输出变为1。输出并停止：";
for(int j=0;j<11;j++)
{
cout<<shuru[j];
}
cout<<endl;
break;
}
}
return 0;
}
void main()
{
TL t;
t.panduan();//对象t调用panduan()
}
测试及调试
键盘输入拓展二进制编码010010110000，求得XN*2为001001001100.即5的2倍为10。
五.总结
理解图灵机拓展二进位的乘2运算，了解内态和输出的变化。本程序可自行输入拓展二进位编码，从而得出XN*2结果。缺点是：当二进制编码数大于设定的数组长度时，需改动panduan()函数中循环次数，改动地方过多。程序可进一步优化为将最终输出拓展二进位编码转换为二进制，最终转为十进制，便于观察。 | 
转播
