1936年 A.M.Turing 发表了一篇论文[1],其中给出了一种在机器上自动运算的计算模型,由此开创了“自动机”这一学科分支。通用图灵机向人们展示这样一个过程:程序和其输入可以先保存到存储带上,图灵机就按程序一步一步运行直到给出结果,结果也保存在存储带上。更重要的是,隐约可以看到现代计算机主要构成,尤其是冯?诺依曼理论的主要构成[2]。
图1 图灵机的概念图
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
如上所示:3+2的表示。
计算3+2;
表1 3+2加法图灵机运算步骤表
步数 |
状态 |
纸带 |
1 |
00 |
0000001110110000 |
2 |
00 |
0000001110110000 |
3 |
00 |
0000001110110000 |
4 |
00 |
0000001110110000 |
5 |
00 |
0000001110110000 |
6 |
00 |
0000001110110000 |
7 |
00 |
0000001110110000 |
8 |
01 |
0000001110110000 |
9 |
01 |
0000001110110000 |
10 |
01 |
0000001110110000 |
11 |
10 |
0000001111110000 |
12 |
10 |
0000001111110000 |
13 |
10 |
0000001111110000 |
14 |
11 |
0000001111110000 |
15 |
00 |
0000001111000000 |
|
|
--停机-- |
C/C++代码如下:
#include <cstdio> #define Max 16 int main() { int num[Max]; // 纸带 int state[3]={0,0,0}; // 初始状态00 int sum=0 , step=0; // 和;步数 for(int i=0; i<Max; i++) { scanf("%d",&num[i]); if(num[i] > 1 || num[i] < 0) // 只能输入0和1 { printf("输入有误!请重新输入:\n"); i=i-1; } } printf("\n-----------------------开始---------------------------\n"); // 图灵机开始扫描 for(int i=0; i<Max; i++) { state[2] = num[i]; // 读入 step++; printf("第%d步\t",step); // 测试 1: 输出状态 for(int j=0; j<3; j++) printf("%d", state[j]); printf("\t"); // 判断 if(state[0]==0) { if(state[1]==0) { if(state[2]==1) { state[0]=0; state[1]=1; // 如果是00,1就转变为01,1 state[2]=0; num[i]=1; // 如果是01,0就转变为10,1 } } else { if(state[2]==0) { state[0]=1; state[1]=0; state[2]=1; num[i]=1; // 如果是01,0就转变为10,1 } } } else { if(state[1]==0) { if(state[2]==0) // 退位有问题?? { num[i]=0; // 如果是10,0就返回1位并把状态改为11,0 state[0]=1; state[1]=1; i = i-2; } } else { if(state[2]==0) { printf("Error!\n"); return 0; } else { num[i]=0; // 如果是11,1就把状态改为00,0且输出 for(int j=0; j<Max; j++) printf("%d ", num[j]); printf("\n-----------------------结束---------------------------\n"); for(int i=0; i<Max; i++) sum += num[i]; printf("加法图灵机的结果为:%d", sum); return 0; } } } // 测试 2: 输出处理过程 for(int j=0; j<Max; j++) printf("%d ", num[j]); printf("\n"); } }
AddingTuringMachine.cpp测试结果如下:
/** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // bug,没有结束标记;结束标记是11,1但是此处没有 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 // 16位的纸带,最大和数为 14?? 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 // 越界,bug */ /** bug 1: 全为 0 的 16 位纸带(个人认为这个不是 bug); bug 2: 10+6 的 16 位纸带(解决方法: 1、增长纸带(新增部分初始值为 0); 2、增加判断条件!) */
[1] A.M.Turing.ON COMPUTABLE NUMBERS,WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM.1936,5(28).
[2] 罗琼主编;杨微副主编;卢青华,张莉娜,袁丽娜,陈孝如参编.计算机科学导论:北京邮电大学出版社,2016.08:第36页
a b
图2 a图为博主的公众号二维码,b图为图灵的照片
原文:https://www.cnblogs.com/jianle23/p/13704318.html