第二次上机《图灵机》
一．题目
图灵机
1.实验目的
1.掌握图灵机的概念和基本结构，理解图灵机的基本指令和编码方式；
2.掌握图灵机的编程方法。
2.实验内容
对于任意给定的一台Turing机和任意给定的字符串w ( w不含空格)，编程模拟此Turing机的运行过程，要求输出从开始运行起的每一步骤的结果。
3.要求
完成实验报告包含以下内容：
1.题目分析
2.算法构造
在此论证算法设计中的一些必要的设计依据。
3.算法实现
程序源代码（请写入必要的注释）。
4.调试、测试及运行结果
5.经验归纳
二．分析
模拟图灵机的运算过程，分为下面几个步骤:
1.输入一个十进制数，将其转化成二进制；
void convert(int s)
{
if(s==0)
cout<<0;
else
{
convert(s/2);
cout<<s%2;
}
}
2.将二进制数扩展成图灵机编码:
（1）1换成10;
（2）0换成0；
（3）末尾加逗号‘，’，即110；
void shift(int i)
{
int n,j;
int m[20];
m[i]=110; //末尾加“，”，为110
for(j=0;j<i;j++)
{
cout<<"按位输入（从高到低）:"<<endl;
cout<<"第"<<j+1<<"为:";
cin>>m[j];
}
for(n=0;n<i;n++)
{
if(m[n]==0)
{
m[n]=0;
}
else
m[n]=10;
}
//输出图灵机编码
cout<<"图灵机编码为:";
for(int t=0;t<i+1;t++)
{
cout<<m[t];
}
cout<<endl;
}
3.执行UN+1图灵机,命令如下：
（1）0 0->0 0 R （2）0 1->1 1 R （3）1 0->0 1 STOP （4）1 1->1 1 R
void do_1(char tur[20])
{
int p,q;
int c_status=0; //当前状态默认为0
for(p=0;q!=0&&p<strlen(tur);p++)
{
cout<<"步骤"<<p+1<<":"<<endl;
cout<<"当前内态:"<<c_status<<" "<<"当前输入:"<<tur[p]<<endl;
//1.内态为0, 输入为0,则内态仍为0，输出为0
if(c_status==0&&tur[p]=='0')
{
c_status=0;
tur[p]='0';
cout<<"动作:R,即向右移动一格!"<<endl;
cout<<"步骤"<<p+1<<"运行后的结果:"<<tur<<endl;
}
//2.内态为0 输入为1,则内态变为1，修改当前输出位为1
else if(c_status==0&&tur[p]=='1')
{
c_status=1;
tur[p]='1';
cout<<"动作R,即向右移动一格!"<<endl;
cout<<"步骤"<<p+1<<"运行后的结果:"<<tur<<endl;
}
//3.内态为1 输入为0 ,则内态变为0，修改当前输出位为1
else if(c_status==1&&tur[p]=='0')
{
c_status=0;
tur[p]='1';
q=1;
cout<<"新的内态:"<<c_status<<" ";
cout<<"当前输出:"<<tur[p]<<endl;
cout<<"STOP 运行结束!"<<endl;
break;
}
//4.内态为1 输入为1 ,则内态变为1，修改当前输出位为1
else if(c_status==1&&tur[p]=='1')
{
c_status=1;
tur[p]='1';
cout<<"动作:R,即向右移动一格!"<<endl;
cout<<"步骤"<<p+1<<"运行后的结果:"<<tur<<endl;
}
cout<<"新的内态:"<<c_status<<" ";
cout<<"当前输出:"<<tur[p]<<endl;
}
cout<<"结束后的运行结果:"<<tur<<endl;
}
4.执行XN*2图灵机，命令如下:
（1）0 0->0 0 R
（2）0 1->1 0 R
（3） 0->0 1 R
（4）1 1->10 0 R
（5）10 0->11 1 R
（6）11 0->0 1 STOP
void do_2(char tu[20])
{
int e;
int ch_status=0; //默认当前状态为0
for(e=0;e<strlen(tu);e++)
{
cout<<"步骤"<<e+1<<":"<<endl;
cout<<"当前内态:"<<ch_status<<" "<<"当前输入:"<<tu[e]<<endl;
//1.内态为0, 输入为0,则内态仍为0，输出为0
if(ch_status==0&&tu[e]=='0')
{
ch_status=0;
tu[e]='0';
cout<<"动作:R,即向右移动一格!"<<endl;
cout<<tu<<endl;
}
//2.内态为0, 输入为1,则内态仍为1，输出为0
else if(ch_status==0&&tu[e]=='1')
{
ch_status=1;
tu[e]='0';
cout<<"动作:R即向右移动一格!"<<endl;
cout<<tu<<endl;
}
//3.内态为1, 输入为0,则内态仍为0，输出为1
else if(ch_status==1&&tu[e]=='0')
{
ch_status=0;
tu[e]='1';
cout<<"动作:R向右移动一格!"<<endl;
cout<<tu<<endl;
}
//4.内态为1, 输入为1,则内态仍为10，输出为0
else if(ch_status==1&&tu[e]=='1')
{
ch_status=10;
tu[e]='0';
cout<<"动作:R向右移动一格!"<<endl;
cout<<tu<<endl;
}
//5.内态为10, 输入为0,则内态仍为11，输出为1
else if(ch_status==10&&tu[e]=='0')
{
ch_status=11;
tu[e]='1';
cout<<"动作:R向右移动一格!"<<endl;
cout<<tu<<endl;
}
//6.内态为11, 输入为0,则内态仍为0，输出为1
else if(ch_status==11&&tu[e]=='0')
{
ch_status=0;
tu[e]='1';
cout<<"动作:STOP因运行结束!"<<endl;
cout<<tu<<endl;
break;
}
cout<<"新的内态:"<<ch_status<<" ";
cout<<"当前输出:"<<tu[e]<<endl;
}
cout<<"运行结果:"<<tu<<endl;
}
四.源代码
#include<iostream>
#include<string>
using namespace std;
void convert(int s)
{
if(s==0)
cout<<0;
else
{
convert(s/2);
cout<<s%2;
}
}
//二.二进制数扩展成图灵机编码
//1->10
//0->0
//末尾加’,’->110
void shift(int i)
{
int n,j;
int m[20];
m[i]=110; //末尾加“，”，为110
for(j=0;j<i;j++)
{
cout<<"按位输入（从高到低）:"<<endl;
cout<<"第"<<j+1<<"为:";
cin>>m[j];
}
for(n=0;n<i;n++)
{
if(m[n]==0)
{
m[n]=0;
}
else
m[n]=10;
}
//输出图灵机编码
cout<<"图灵机编码为:";
for(int t=0;t<i+1;t++)
{
cout<<m[t];
}
cout<<endl;
}
//三.图灵机编码的执行过程UN+1
//0 0->0 0 R
//0 1->1 1 R
//1 0->0 1 STOP
//1 1->1 1 R
void do_1(char tur[20])
{
int p,q;
int c_status=0; //当前状态默认为0
for(p=0;q!=0&&p<strlen(tur);p++)
{
cout<<"步骤"<<p+1<<":"<<endl;
cout<<"当前内态:"<<c_status<<" "<<"当前输入:"<<tur[p]<<endl;
//1.内态为0, 输入为0,则内态仍为0，输出为0
if(c_status==0&&tur[p]=='0')
{
c_status=0;
tur[p]='0';
cout<<"动作:R,即向右移动一格!"<<endl;
cout<<"步骤"<<p+1<<"运行后的结果:"<<tur<<endl;
}
//2.内态为0 输入为1,则内态变为1，修改当前输出位为1
else if(c_status==0&&tur[p]=='1')
{
c_status=1;
tur[p]='1';
cout<<"动作R,即向右移动一格!"<<endl;
cout<<"步骤"<<p+1<<"运行后的结果:"<<tur<<endl;
}
//3.内态为1 输入为0 ,则内态变为0，修改当前输出位为1
else if(c_status==1&&tur[p]=='0')
{
c_status=0;
tur[p]='1';
q=1;
cout<<"新的内态:"<<c_status<<" ";
cout<<"当前输出:"<<tur[p]<<endl;
cout<<"STOP 运行结束!"<<endl;
break;
}
//4.内态为1 输入为1 ,则内态变为1，修改当前输出位为1
else if(c_status==1&&tur[p]=='1')
{
c_status=1;
tur[p]='1';
cout<<"动作:R,即向右移动一格!"<<endl;
cout<<"步骤"<<p+1<<"运行后的结果:"<<tur<<endl;
}
cout<<"新的内态:"<<c_status<<" ";
cout<<"当前输出:"<<tur[p]<<endl;
}
cout<<"结束后的运行结果:"<<tur<<endl;
}
//四.图灵机编码的执行过程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
void do_2(char tu[20])
{
int e;
int ch_status=0; //默认当前状态为0
for(e=0;e<strlen(tu);e++)
{
cout<<"步骤"<<e+1<<":"<<endl;
cout<<"当前内态:"<<ch_status<<" "<<"当前输入:"<<tu[e]<<endl;
//1.内态为0, 输入为0,则内态仍为0，输出为0
if(ch_status==0&&tu[e]=='0')
{
ch_status=0;
tu[e]='0';
cout<<"动作:R,即向右移动一格!"<<endl;
cout<<tu<<endl;
}
//2.内态为0, 输入为1,则内态仍为1，输出为0
else if(ch_status==0&&tu[e]=='1')
{
ch_status=1;
tu[e]='0';
cout<<"动作:R即向右移动一格!"<<endl;
cout<<tu<<endl;
}
//3.内态为1, 输入为0,则内态仍为0，输出为1
else if(ch_status==1&&tu[e]=='0')
{
ch_status=0;
tu[e]='1';
cout<<"动作:R向右移动一格!"<<endl;
cout<<tu<<endl;
}
//4.内态为1, 输入为1,则内态仍为10，输出为0
else if(ch_status==1&&tu[e]=='1')
{
ch_status=10;
tu[e]='0';
cout<<"动作:R向右移动一格!"<<endl;
cout<<tu<<endl;
}
//5.内态为10, 输入为0,则内态仍为11，输出为1
else if(ch_status==10&&tu[e]=='0')
{
ch_status=11;
tu[e]='1';
cout<<"动作:R向右移动一格!"<<endl;
cout<<tu<<endl;
}
//6.内态为11, 输入为0,则内态仍为0，输出为1
else if(ch_status==11&&tu[e]=='0')
{
ch_status=0;
tu[e]='1';
cout<<"动作:STOP因运行结束!"<<endl;
cout<<tu<<endl;
break;
}
cout<<"新的内态:"<<ch_status<<" ";
cout<<"当前输出:"<<tu[e]<<endl;
}
cout<<"运行结果:"<<tu<<endl;
}
//主函数
int main()
{
//一.二进制转十进制
int s;
cout<<"请输入一个十进制的正整数:";
cin>>s;
cout<<s<<"的二进制数为:";
{
if(s>=0&&(s%2==0||s%2==1))
{
convert(s);
cout<<endl;
}
else
cout<<"输入错误，请输入‘一个是十进制的正整数’!"<<endl;
}
//二.把二进制数扩展成图灵机编码
int m;
cout<<"请输入二进制的位数:";
cin>>m;
shift(m);
//三.图灵机编码的执行过程XN+1
char tur[20]; //定义一个字符数组，用来存放图灵机编码
cout<<"UN+1:"<<endl;
cout<<"请输入图灵机编码:";
cin>>tur; //输入图灵机编码
do_1(tur);
//四.图灵机编码的执行过程XN*2
char tu[20]; //定义一个字符数组，用来存放图灵机编码
cout<<"XN*2:"<<endl;
cout<<"请输入一个图灵机编码（即扩展后的二进制编码）:";
cin>>tu; //输入图灵机编码
do_2(tu);
return 0;
}
五.个人总结
这次的上机作业刚开始看起来是挺难的，但是认真的分析，把它模块化出来就不是很难了。就分为四个部分：（1）十进制转二进制；（2）二进制扩展成图灵机编码；（3）执行UN+1图灵机；（4）执行XN2图灵机。十进制转二进制我开始用的是数组，把每一步的余数存进数组，再逆向输出数组。后来，觉得这种方法有点麻烦，就在网上查阅了递归调用的方法，其实这个挺方便的，直接就可以输出二进制，唯一不足的就是最高位的0没有去掉。
十进制扩展成图灵机编码这个不难，遇到1转换成10，0就是0，末尾加逗号，即110。
最难的就是UN+1以及XN2的执行过程了，要求输出每一步的过程和最终的结果。这个，认真分析分析，其实也就是分情况嘛，搞清楚它每一步的内态，输入，以及下一步的变化。再用if-else的嵌套就可以了。
当时老师上课讲图灵机的时候我真的觉得有点难，但是当做完这个作业的时候就特别清楚，它执行的每一步也都明白为什么。所以，理论还是要靠实践来巩固的！