图灵机与计算.ppt

计 算 引 论
——图灵机与计算
国外究竟为什么能发明出各式各样的计算机呢？
这一切的源头都来源于计算理论
一、计算机的极限
计算机能做什么？
人们倾向于考虑还算简单的、带有良好结构的问题，而这些问题计 算 引 论
——图灵机与计算
国外究竟为什么能发明出各式各样的计算机呢？
这一切的源头都来源于计算理论
一、计算机的极限
计算机能做什么？
人们倾向于考虑还算简单的、带有良好结构的问题，而这些问题是可判定的。不可判定的问题比可判定的问题多得多。
main()
{
printf(“hello, world\n”);
}
int exp(int i,n)/*计算i的n次幂*/
{
int ans, j;
ans =1;
for (j=1; j<=n; j++) ans *=i;
return(ans);
}
main()
{
int n, total, x, y, z;
scanf(“%d”, &n);
total = 3;
while (1) {
for (x=1; x<=total-2; x++)
for (y=1; y<=total-x-1; y++) {
z = total – x –y;
if (exp(x,n) + exp(y,n) == exp(z,n))
printf(“hello, world/n”);
}
total++;
}
}
对任何整数n>2，程序能不能找到满足的正整数三元组？
一、计算机的极限（续）
关于计算理论可以追溯到1900年，当时著名的大数学家希尔伯特在世纪之交的数学家大会上给国际数学界提出了著名的23个数学问题。其中第十问题是这样的：是否存在着一个通用过程，这个过程能用来判定任意数学命题是否成立，即，输入一个数学命题，在有限时间内，能证明该命题成立或不成立。
1931年哥德尔发表了著名的不完全性定理。这个定理表明了一个逻辑系统的限度，也潜含着对于计算机所能够从事的工作的范围的限制；任何一个数学的公理化体系都不是“完美的”。换个角度说，任何数学公理化系统都是死的，它总需要人为地从外界注入新的公理进去才能让它日趋完善，而它自己并不能完全自动避免矛盾产生。
二、图灵的伟大成就
上帝创造了人；图灵创造了计算机
计算机之父
人工智能之父
计算机的基本概念属于图灵。
冯·诺依曼的基本作用是使世界认识了由图灵引入的计算机基本概念……
图灵机的产生一方面奠定了现代数字计算机的基础（后来冯诺依曼就是根据图灵的设想才设计出第一台计算机的）。另一方面，根据图灵机这一基本简洁的概念，我们还可以看到可计算的极限是什么。
三、图灵机
这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。（中间那个大盒子），内部状态（盒子上的方块，比如A,B,E,H），另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。
当前内部状态s 输入数值i 输出动作o 下一时刻的内部状态s'
B 1 前移 C
A 0 往纸带上写1 B
C 0 后移 A
… … … …
四、理解图灵机
建模：
（1）小虫、纸带、方格
（2）黑色或者白色的信息就是小虫的输入信息
（3）小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格
（4）行动的规则
程序1：
程序2：
1
2
3
程序2
4
5
6
7
程序3
我们每一个会决策、会思考的人就可以被抽象的看成一个图灵机。
扩展刚才说的小虫模型 ，把小虫的输入集合、输出行动集合、内部状态集合进行扩大
五、计算
1、什么是计算？
2、计算的组合
3、征服无限的方法
4、归纳
六、模拟
1、什么是模拟？
2、图灵机之间的模拟
六、模拟（续）
3、计算等价性
模拟的一个关键作用就是阐明什么是等价的。
4、意义
“请把窗户关上！”，
“Please close the window！”，
“01001110111”
如果把中国人、英国人、机器人都看作是图灵机，而那三句话看作是对他们的输入信息，那么最终的结果就是图灵机计算的输出。
七、万能图灵机
这种能够模拟其他所有图灵机的图灵机就叫