从数学的角度讲,程序定义了一函数,以程序的输入和程序启动前的机器状态为自变量,以计算输出为因变量的一个函数。和数学中定义的函数不同的是,程序定义的函数是不完全的。即是指对某些输入可能没有确定的输出,可能是因为运行程序时出错(Runtime Error),也可能是程序无限循环下去(Nontermination). 所以在计算机领域,探讨的函数是不完全的,是partial的。
函数在数学的精确定义是符合两个条件的关系,假设A,B为非空集合
f ⊆ A ×
B是一个数学意义上的函数,只有当
- 如果<x, y>
∊ f 并且 <x, z>
∊ f , 可以推出y=z;
- 对每个 属于A的值x,存在一个y ∊ B
,使得<x, y>∊ f.
成立时。
在计算机领域函数的精确定义不需要满足第2个条件,其他一样。也就是
f ⊆ A ×
B是一个partial函数,只有当
- 如果<x, y>
∊ f 并且 <x, z>
∊ f , 可以推出y=z;
成立时。
也许你对用数学函数来表达程序不是很赞同,你可能觉得数学函数的对象就是数字,怎么用数字来表达键盘操作,鼠标点击,网页刷新等等东西呢? 首先函数的对象可以不是数字,函数的定义域和值域可以是任意对象。其次,即是只考虑对象是数字的函数,也可以表达所有的程序。即使只是对象是自然数的函数,也足够了。因为象键盘操作,网页刷新等等都可以用数字来编码,那么程序只不过读取一些数字,修改一些,输出一些。实际上,如果你抛开键盘鼠标显示器,想像一下计算机的内部,就是如此的。换句话说,只考虑计算数字的程序,并不改变程序的本质,并不改变程序到底可以完成什么的能力。
用以上的观点,我们可以把每个程序,不管是Java的还是什么哇的,等价于一个函数。
反过来,我们可以把每个函数等价于一个程序吗? 也就是说为每个函数,写一个程序计算它的关系。答案是否定。并不是每个函数都可以计算的,存在不可计算的函数,比如著名的Halting问题。通俗的讲,Halting问题是指判断任意一个程序是否会在有限的时间里停止。这是不可计算的。如果你能写出一个程序,用任何一门语言,可以正确判断所有的Java程序里面是否存在无限循环。你马上就轰动世界,拿Turing奖,诺贝尔奖如探囊取物。
Halting问题有多种证明方法,但都是用反证法,假设Halting问题是可以解决的,那么我们可以推出一个谬论。详情请看有关可计算理论的书籍。
转载请保留
http://www.blogjava.net/xilaile/archive/2007/05/03/115095.html