文档介绍：第二章计算理论与计算模型
第一页，共57页。
计数与计算
手指、石头、结绳计数，算筹计算
计算的几种视角
圆周率:10万亿位
*
第二页，共57页。
许多计算领域的求解问题，如计程，对给定的一个输入，能在有限步内给出答案，那么这个问题是可计算性的。
定义：凡可用某种程序设计语言描述的问题都是可计算性问题。
特性：确定性、有限性、机械性、可执行性、终止性。
计算理论
*
第十二页，共57页。
图灵给出的可计算性定义：能够在图灵机上执行的过程（通常又称算法的过程）。
图灵之所以能取得成功，是他采用了算法思维来研究计算的过程，从而揭示可计算性的概念。
算法思维与目前在计算机上运行的程序之间有着密切的关系，从而使他的理论受到重视并被广泛使用。
计算理论
*
第十三页，共57页。
3、可计算性理论的主要内容
图灵机：用于精确描述算法的特征。可以用图灵机来计算其值的函数是可计算函数，找不到图灵机来计算其值的函数是不可计算函数。
λ演算：它是一种定义函数的形式演算系统。该系统引进λ记号以明确区分函数和函数值，并把函数值的计算归结为按照一定规则进行一系列演算和转换。
计算理论
*
第十四页，共57页。
丘奇-图灵论题：丘奇说，λ可定义函数类与直观可计算函数类相同。图灵说，图灵机可计算函数类与直观可计算函数类相同。因此可以说，图灵机可计算函数类与λ可定义函数类相同。
原始递归函数：规定少量直观可计算的函数为原始递归函数，原始递归函数的合成仍然是原始递归函数，可以由已知原始递归函数简单递归计算出函数值的函数仍然是原始递归函数。
计算理论
第十五页，共57页。
计算理论
可计算性理论的基本思想、概念和方法被广泛应用于计算科学的各个领域。
数学模型的建立方法在科学、工程、技术领域中被广泛采用。
递归的思想被用于程序设计、数据结构和计算机体系结构。
λ演算被用于研究程序设计语言的语义。
*
第十六页，共57页。
计算学科的一个基本结论是不可计算的函数要比可计算的函数多得多。
虽然许多问题是可判定的，但更多的问题是不可判定的。
例如：停机问题和波斯特对应问题都是不可判定的。
计算理论
*
第十七页，共57页。
停机问题
停机问题是目前逻辑数学的焦点和第三次数学危机的解决方案，它是重要的不可判定问题。
1936年，Turing发表“论可计算数及其在判定问题中的应用”论文中提出一般性停机问题的不可判定性，并用形式化方法证明其为一个不可计算问题。
一般性的停机问题：对于任意的图灵机和输入，是否存在一个算法，用于判定图灵机在接收初始输入后可达停机状态。若能找到这种算法，停机问题可解；否则不可解。
计算理论
*
第十八页，共57页。
通俗地说，停机问题就是判断任意一个程序是否在有限的时间内结束运行的问题。
例如：main()
{ int i=1;
while ( i<10 )
{ i=i+1;
}
return;
}
又如：main()
{ int i=1;
while ( i>0 )
{ i=i+1;
}
return;
}
程序可终止
程序死循环
程序简单时容易做出判断，当示例复杂时会遇到较大的困难，而在某些情况下则无法预测。
计算理论
*
第十九页，共57页。
停机问题的关键：能否找到一个测试程序，这个测试程序能判定任何一个程序在给定的输入下能否终止。
数学反证法证明：先假设存在这样的测试程序，然后再构造一个程序，该测试程序不能测试
假设存在一个测试程序T，它能接受任何输入。
当输入程序P能终止，输出1；
P不能终止，输出0。
计算理论
*
第二十页，共57页。
P能终止,X→1
P不终止,X→0
测试程序T
程序P
X
测试程序T
X(1或0)
while(x)
{
}
S
程序P
测试程序T
X(1或0)
while(x)
{
}
S
程序S
P终止,X→1,S→不终止
P不终止,