模拟图灵机
1.实验内容
对于任意给定的一台Turing机和任意给定的字符串w（不含空格），编程模拟此Turing机的运行过程，要求输出从开始运行起的每一步的结果。
2.题目分析
本实验实现模拟一台Turing机的运行过程，最重要的是要理解图灵机在纸带上是如何运行的。我选择的是采用XN2的运算指令。整体的实现过程是：输入十进制数—转换成二进制—转换成纸带上二进制的扩展—进行指令XN2运算—输出扩展二进制—转换成二进制数—输出十进制数。
3.算法构造
第一步：十进制转二进制。利用循环将输入的十进制数进行模2运算，利用数组a[]保存；
第二步：扩展二进制。扩展二进制时1表示为10，0依然是0，逗号表示为110，利用循环将扩展二进制用数组b[]保存；
第三步：XN2指令运算。定义一个长度为2的数组d[]来存放内态和输入，d[0]存放图灵机内态，d[1]存放输入。利用循环将扩展二进制的值赋值给d[1]进而实现XN2的指令操作，循环结束后末尾加逗号（110）。
第四步：扩展二进制转换为二进制。转换时，010转换为1，00转换为0。利用循环将转换后的二进制数保存在数组c[]中。并统计二进制数的位数为下一步做准备。
第五步：二进制转换成十进制数。利用pow()函数将二进制从低位到高位转换
4.算法实现
#include<stdio.h>
#include<math.h>//使用pow()函数
void main()
{
int num,m,i=0,sum=0,num2=0;//num为键盘输入的十进制整数，sum为二进制的位数，num2为进行指令后的十进制数，m为取余
int a[100]; //a[100]存放十进制转换成的二进制
int b[100]={0}; //b[100]存放打印在纸带上的扩展二进制
int c[]={0}; //c[]存放运行指令后的二进制
int d[2]={0}; //d[2]存放XN*2指令的内态和输入
printf("请输入一个正整数:\n");
scanf("%d",&num);
while(num>0) //将十进制转换为二进制
{
m=num%2;
a[i]=m;
num=num/2;
i++;
}
printf("将该正整数转换成二进制数:\n");
for(i--;i>=0;i--) //倒序输出二进制
{
printf("%d",a[i]);
sum++;
}
printf("\n");
//将二进制数打印到磁带上
b[0]=0;
i=1;
for(int j=0;j<sum;j++) //1表示为10，0依然是0，逗号表示为110
{
if(a[j]==1)
{
b[i++]=1;
b[i++]=0;
}
else
b[i++]=0;
}
//扩展二进制末尾加逗号（110）
b[i++]=1;
b[i++]=1;
b[i++]=0;
printf("将二进制数打印在磁带上:\n");
sum=0;
for(j=0;j<i;j++)
{
printf("%d",b[j]);
sum++;
}
printf("\n");
printf("实现图灵机XN*2的指令运算:\n");
d[0]=0; //d[0]存放图灵机内态
for(j=0;j<sum-1;j++)
{
d[1]=b[j]; //将XN*2指令的输入赋值给d[1]
if(d[0]==0&&d[1]==0) //内态为0，输入为0时
{
d[0]=0;
b[j]=0;
printf("%d\t",b[j]);
}
else if(d[0]==0&&d[1]==1) //内态为0输入为1时
{
d[0]=1;
b[j]=0;
printf("%d\t",b[j]);
}
else if(d[0]==1&&d[1]==0) //内态为1，输入为0时
{
d[0]=0;
b[j]=1;
printf("%d\t",b[j]);
}
else if(d[0]==1&&d[1]==1) //内态为1，输入为1时
{
d[0]=10;
b[j]=0;
printf("%d\t",b[j]);
}
else if(d[0]==10&&d[1]==0) //内态为10，输入为0时
{
d[0]=11;
b[j]=1;
printf("%d\t",b[j]);
}
else if(d[0]==11&&d[1]==0) //内态为11，输入为0时
{
d[0]=0;
b[j]=1;
printf("%d\t",b[j]);
break; //STOP
}
}
b[j++]=1; //末尾加上逗号（110）
b[j++]=1;
b[j++]=0;
printf("\n");
printf("运行指令后，磁带上的结果为:\n");
for(i=0;i<j;i++)
printf("%d",b[i]); //输出XN*2的扩展二进制结果
printf("\n");
printf("将磁带上的结果转换成二进制:\n");
sum=0;
for(i=1,j=0;;i++,j++)
{
if(b[i]==0&&b[i+1]==1&&b[i+2]==0)//010转换为1
{
c[j]=1;
printf("%d",c[j]);
sum++; //记录二进制的位数
i++;
}
else if(b[i]==0&&b[i+1]==0)//00转换为0
{
c[j]=0;
printf("%d",c[j]);
sum++;
}
else
break;
}
printf("\n");
//将二进制转换为十进制
for(i=sum-1;i>=0;i--) //循环将结果转换为十进制
num2=num2+c[i]*(int)pow(2,(sum-1-i));//从低位到高位
printf("十进制结果为：%d\n",num2);
}
5.调试及运行结果
5.1运行结果
5.2调试结果
6.经验归纳
6.1问题与不足
1.将二进制转换为扩展二进制时，错把逗号（110）放入循环中，使得结果总是不对。
2.XN*2指令运算一开始用flag表示内态，用数组表示输入，但循环一直进不去。后请教同学改为用一个数组存放内态和输入。
3.这个程序全部写在了main()函数中，没有将各个步骤用一个个子函数实现。
6.2总结
刚开始是没有头绪的，想不明白怎么模拟图灵机，尤其是想不明白怎么把二进制打印在纸带上，不过后来还是弄清楚了，在整个过程中，遇到了很多问题，感觉自己逻辑没有问题，而且程序编译也没有错，可结果就是不对，又或是有个循环没有进去。最让自己崩溃的是自己还看不出来哪里不对，只好请同学帮忙查错。有时一个小小的问题别人一看就看出来了，自己是看N遍都觉得没错啊。这次的程序我唯一不满意的地方是把所有的代码都写在了main()函数里，希望自己后面可以再改进自己的程序，试试把一些步骤放在子函数里，调用它。