一、问题描述 设计一个图灵机，实现二进制数 x 的加 1 运算，同时保存进位。最高位如 果有进位的话可以保存该进位。 二、实现思路 1、图灵机设计： 图灵机 M 是一个七元组，M=（Q，∑，Γ，δ，q0，B，F），Q：状态的有 穷集合；∑⊆Γ-｛B｝为输入字母表；Γ：带符号表； q0：q0∈Q 是 M 的开始状 态； B：B∈Γ称为空白符；F：F∈Q 是终止状态集合；δ：M 的转换函数。 在该 x+1 图灵机中，开始状态为 s，终止状态为 f，状态集合 Q 为{s,A,B,f}， 空白符为*，字母表为{0,1}，进位标志位 c，状态转移函数如下： 状态 A：表示无进位的加法；状态 B：表示有进位加法 状态转移函数为： δ（s,0）=(A,1,L) δ（s,1）=(B,0,L) δ（A,0）=(A,0,L) δ（A,0）=(A,1,L) δ（B,0）=(A,1,L) δ（B,1）=(B,0,L) δ（A,*）=(f,*,R) c=0 c=1 c=0 c=0 c=0 c=1 2、实现过程 初始化图灵机，分别初始化数据带为*0，这样结束符就是*，最左端的 0 是 为了接收最高位的进位，如果有溢出的话直接丢弃可能使得计算结果不正确。然 后是接收输入二进制数 x，将该数据初始化到图灵机数据带上。初始化状态带为 初始状态 s，初始化进位标志位 0。然后就是按照状态转移函数开始执行，修改 数据带，状态带，和进位标志，遇到最左端的*时终止图灵机的执行，同时输出 此时图灵机的数据带数据，和状态带状态，以及进位标志位，最后输出计算结果。 三、实现程序 #include #include #include #define MAX_num 100 

char x[MAX_num]; char str[MAX_num]; char s[4]="s"; int c=0;//进位标志位 /*状态个数：4；状态名： S,A,B,F; 字母表：0,1,*; 状态说明： s：表示初始状态 A：表示为进位状态 B：表示有进位状态 f：表示结束状态 字母表说明： 0,1，*，都是课识别的字符，其中*表示结束字符 */ void show(char str[],char s[],int c) { printf("\n 运算之后图灵机状态 \n"); printf("\n 运算结束时状态：%s",s); printf("\n 运算结束时数据带：%s\n",str); printf("运算结束时进位标志：%d\n\a",c); } void Fun_A(char s[],char str[],int c,int n)//无进位加法状态转移函数 { if(str[n-1]=='0'&&(str[n]=='0'||'1')) Fun_A(s,str,c,n-1); else if(str[n-1]=='*') { strcpy(s,"f"); show(str,s,c); } } void Fun_B(char s[],char str[],int c,int n)//有进位加法状态转移函数 { if(str[n]=='0') { str[n]='1'; strcpy(s,"A"); c=0; Fun_A(s,str,c,n-1); } 

else if(str[n]=='1') { str[n]='0'; Fun_B(s,str,c,n-1); } } { void show_x(char str[],char x[])//，输出最后计算结果，即将数据带字符数组 中的数值复制给 x int i=0,j=0; int n=strlen(str)-2; while(j<=n) { if(str[j]=='1') x[i++]='1'; else if(str[j]=='0') j=j+1; x[i++]='0'; } x[i]='\0'; printf("\n\n 运算结果 x:"); printf("%s\n",x); } void init(int n,char str[]){//初始化图灵机 int i=0; while(i

printf("\n 初始化数据带：%s\n",str); printf("初始化进位标志：%d\n",c); } void start(int n){ //执行开始函数 if(str[n]=='0') { strcpy(s,"A"); str[n]='1'; c=0; Fun_A(s,str,c,n-1); } else if(str[n]=='1') { strcpy(s,"B"); str[n]='0'; c=1; Fun_B(s,str,c,n-1); } } int main () { int b=1; int i=0; int n; x[0]='\0';//初始化 x 字符数组，也就是存放要进行加 1 运算的字符的数组 printf("\t\t\t 实现 X+1 图灵机"); printf("\n 请输入 x (用 2 进制表示)："); scanf("%s",x); strcpy(str,"*0");//这里是开始将*0 放进 str 中，0 是为了保存进位，初始 化图灵机数据带 n=strlen(x);//获取 x 的长度 init(n,str);//调用初始化函数，对图灵机进行初始化 n=strlen(str)-2; start(n); show_x(str,x); return 0; 

} 四、执行结果 五、心得体会 形式语言与自动机学习完之后设计了一份关于图灵机的作业，但是那个时候 是设计，没有使用代码实现，在实现的过程才发现，理论设计在设计到数据访问 和保存的时候需要一些改进，因为在设计的时候并没有转换成代码实现，当实现 的时候就需要了抽象思维，将设计的模型转换成可以实现的模型。我越来越发现 计算机思维的重要性。