int state;//记录当前状态
int currentpos;//记录当前位置
int halt;//退出
int i;//临时辅助变量
int s;//临时存储状态
char tape[N];//纸带长度
char number[M];//存储x
char c1;//临时存储字符
char c2;//临时存储字符
}
for(i = S;i < S + M && number[i-S] != '\0';i++) //将数字写入纸带
tape[i] = number[i-S];
currentpos = S;//初始化
halt = 1;//此时state = 1
d = 'R';//初始为右移
cout<<endl<<"其五元组如下："<<endl;
print();
}
}
void state6()//此时d = 'L';
{
while(state == 6)
{
c1 = c2 = tape[currentpos];//暂存
s = state;
if(tape[currentpos] == 'B')//返回状态1
{
state = 1;
currentpos++;
}
else//进入状态2
{
state = 2;
currentpos++;//进入2时d='R'
}
print();
}
}
void state2()//此时d = 'R'
{
while(state == 2)
{
c1 = c2= tape[currentpos];//暂存
s = state;
if(tape[currentpos] == 'B')//进入状态3
char d;//方向输出
void start()
{
for(i = 0;i < N - 1;i++)//初始化纸带
tape[i] = 'B';
tape[N-1] = '\0';
cout<<"使用图灵机计算f(x) = 2^x。其中x为二进制数字。"<<endl;
while(1)//判断二进制
{
state = 1;
for(i = 0;i < N;i++)
if(tape[i] != 'B' && tape[i] != '\0')
{
cout<<tape[i];
outfile<<tape[i];
}
cout<<")二进制"<<endl<<endl;
outfile<<")二进制"<<endl;
}
void main()
{
outfile<<"请输入二进制数字x = ";
outfile<<number<<endl;
outfile<<endl<<"其五元组如下："<<endl;
}
void print()//输出函数
{
cout<<"<Q"<<s<<","<<c1<<","<<c2<<","<<d<<",Q"<<state<<">"<<endl;
{
state = 4;
c2 = tape[currentpos] = '0';
currentpos--;
d = 'L';//进入4时d='L';
}
else
currentpos++;
print();
}
}
void state4()//此时d='L';
{
while(state == 4)
{
c1 = c2 = tape[currentpos];//暂存
s = state;
if(tape[currentpos] == '0')
c2 = tape[currentpos] = '1';
else
if(tape[currentpos] == '1')//进入状态6
{
state = 6;
c2 = tape[currentpos] = '0';
}
currentpos--;//进入6时d='L';
state = 3;
currentpos++;//进入3时d='R';
print();
}
}
void state3()//此时d = 'R';
{
while(state == 3)
{
c1 = c2 = tape[currentpos];//暂存
s = state;
if(tape[currentpos] == '输入二进制数字x = ";
cin>>number;
for(i = 0;i < M && number[i]!= '\0';i++)
if(number[i] >'1' || number[i] < '0')
state = 0;
if(state)
break;
else
cout<<"无效数字。";
三、实验代码
/*****************************************************************
图灵机的模拟过程
计科二班20110801212张琦佳
*****************************************************************/
}
void homework()//写入文件
{
outfile<<"图灵机的实现过程"<<endl;
outfile<<" Turing.........."<<endl;
outfile<<"计科2班张琦佳"<<endl<<endl;
outfile<<"使用图灵机计算f(x) = 2^x。其中x为二进制数字。"<<endl;
start();
homework();
while(halt)
switch(state)
{
case 1 : state1();
case 2 : state2();
case 3 : state3();
case 4 : state4();
case 5 : state5();
case 6 : state6();
if(tape[currentpos] == '0')
currentpos++;
else
if(tape[currentpos] == 'B')//进入状态7
{
state = 7;
c2 = tape[currentpos] = '1';
currentpos--;
d = 'L';//进入7时d='L';
HUNANUNIVERSITY
计算理论导引
实验报告
题目：
图灵机(Turing)的模拟
学生姓名：
学生学号：
专业班级：
计算机科学与技术2班
上课老师：
实验日期：
2014-1-6
一、
1、掌握Turing机的概念。
2、掌握Turing机的运行过程，了解每一个格局的转化。
二、
对于任意给定的一台Turing机和任意给定的字符串w(w不含空格)，编程模拟此Turing机的运行过程，要求输出从开始运行起的每一格局。
d = 'R';//进入1时d='R';
}
else
currentpos--;
print();
}
}
void state7()//此时d= 'L';
{
while(state == 7)
{
c1 = c2 = tape[currentpos];//暂存
s = state;
if(tape[currentpos] == '0')//清零
outfile<<"<Q"<<s<<","<<c1<<","<<c2<<","<<d<<",Q"<<state<<">"<<endl;