(C++)模拟图灵机-简单的UN+1和UN*2
问题描述
对于任意给定的一台Turing机和任意给定的字符串w ( w不含空格),编程模拟此Turing机的运行过程,要求输出从开始运行起的每一步骤的结果。(本文模拟的是UN+1和UN*2的图灵机)
问题分析
注:1>默认初始内态为0。
2>颜色代表立场!红色代表当前内态,绿色代表新的内态,箭头两边为黑色1位的分别代表本位输入和本位输出。
3>R:右移 L:左移 STOP:停止,运算结束
4>UN系列图灵机简单的利用一串n个1代表数n,如1->1,2->11,3->111,4->1111,5->11111.6->111111等
UN+1
UN+1图灵机的运算规则:
00->00R
01->11R
10->01STOP
11->11R
例:对数字2进行UN+1运算(手写勿喷...)
初始:...11000...
UN*2
UN*2图灵机的运算规则:
00->00R
01->10R
10->101L
11->11R
100->110R
101->1000R
110->01STOP
111->111R
1000->1011L
1001->1001R
1010->101L
1011->1011L
例:对数字1进行UN*2运算
初始:..10000...
运行结果
源代码
/*UN图灵机*/
//输入:一串代表的相应十进制数字(用一串n个1代表数字 如:1->1 2->11 3->111 4->1111 5->11111)
//输出:UN+1/UN*2之后得到的结果
#include<iostream>
using namespace std;
/*UN+1*/
void UnPlus1TuringMachine()
{
char oStr[80];
int flag=0;//标志量 继续计算-->1 结束计算-->0
cout<<"输入要实现UN+1的数:(请以一位或多位0作为结束:)";
cin>>oStr;
int status=0;//初始内态为0
for(int i=0;flag!=1;i++)
{
cout<<"当前内态:"<<status<<"\t"<<"当前输入:"<<oStr[i]<<"\n";
if(status==0 && oStr[i]=='0')//内态为0 输入为0
{
status=0;//内态变为0
oStr[i]='0';//在当前位上修改输出位为0
cout<<"......R!"<<endl;
}
else if(status==0 && oStr[i]=='1')//内态为0 输入为1
{
status=1;//内态变为1
oStr[i]='1';//在当前位上修改输出位为1
cout<<"......R!"<<endl;
}
else if(status==1 && oStr[i]=='0')//内态为1 输入为0
{
status=0;//内态变为0
oStr[i]='1';//在当前位上修改输出位为1
flag=1 ;//修改标志量,计算结束
cout<<"......stop!"<<"\n";
}
else if(status==1 && oStr[i]=='1')//内态为1 输入为1
{
status=1;//内态变为1
oStr[i]='1';//在当前位上修改输出位为1
cout<<"......R!"<<endl;
}
cout<<"新的内态:"<<status<<"\t"<<"当前输出:"<<oStr[i]<<"\n";
}
cout<<"UN+1结果:"<<oStr;
}
/*UN*2*/
void UnMultipliedBy2TuringMachine()
{
char oStr[80];
int flag=0;//标志量 继续计算-->1 结束计算-->0
cout<<"输入要实现UN*2的数:\n";
cout<<"输入注意(请以要计算的数个0再加1位0作为结束,如计算11UN+2的结果请输入11000)\n";
cin>>oStr;
int status=0;//初始内态为0
for(int i=0;flag!=1;)
{
cout<<"当前内态:"<<status<<"\t"<<"当前输入:"<<oStr[i]<<"\n";
if(status==0 && oStr[i]=='0')//00->00R
{
status=0;
oStr[i++]='0';
cout<<"......R!"<<"\n";
}
else if(status==0 && oStr[i]=='1')//01->10R
{
status=1;
oStr[i++]='0';
cout<<"......R!"<<"\n";
}
else if(status==1 && oStr[i]=='0')//10->101L
{
status=10;
oStr[i--]='1';
cout<<"......L!"<<"\n";
}
else if(status==1 && oStr[i]=='1')//11->11R
{
status=1;
oStr[i++]='1';
cout<<"......R!"<<"\n";
}
else if(status==10 && oStr[i]=='0')//100->110R
{
status=11;
oStr[i++]='0';
cout<<"......R!"<<"\n";
}
else if(status==10 && oStr[i]=='1')//101->1000R
{
status=100;
oStr[i++]='0';
cout<<"......R!"<<"\n";
}
else if(status==11 && oStr[i]=='0')//110->01STOP
{
status=0;
oStr[i]='1';
flag=1;
cout<<"......stop!"<<"\n";
}
else if(status==11 && oStr[i]=='1')//111->111R
{
status=11;
oStr[i++]='1';
cout<<"......R!"<<"\n";
}
else if(status==100 && oStr[i]=='0')//1000->1011L
{
status=101;
oStr[i--]='1';
cout<<"......L!"<<"\n";
}
else if(status==100 && oStr[i]=='1')//1001->1001R
{
status=100;
oStr[i++]='1';
cout<<"......R!"<<"\n";
}
else if(status==101 && oStr[i]=='0')//1010->101L
{
status=10;
oStr[i--]='1';
cout<<"......L!"<<"\n";
}
else if(status==101 && oStr[i]=='1')//1011->1011L
{
status=101;//内态变为1
oStr[i--]='1';//在当前位上修改输出位为1
cout<<"......L!"<<"\n";
}
cout<<"新的内态:"<<status<<"\t"<<"当前输出:"<<oStr[i]<<"\n";
}
cout<<"UN*2结果:"<<oStr;
}
int main(void)
{
UnPlus1TuringMachine();
cout<<endl;
UnMultipliedBy2TuringMachine();
return 0;
}
注:这里我写的程序还有bug......就是目前输入时必须有一定位数的0,输入纯1有错误......还望高人指点......