gr8vyguy@Blogjava

程序和函数

从数学的角度讲,程序定义了一函数,以程序的输入和程序启动前的机器状态为自变量,以计算输出为因变量的一个函数。和数学中定义的函数不同的是,程序定义的函数是不完全的。即是指对某些输入可能没有确定的输出,可能是因为运行程序时出错(Runtime Error),也可能是程序无限循环下去(Nontermination). 所以在计算机领域,探讨的函数是不完全的,是partial的。

函数在数学的精确定义是符合两个条件的关系,假设A,B为非空集合

fA × B是一个数学意义上的函数,只有当

  1. 如果<x, y>f  并且 <x, z>f  , 可以推出y=z;
  2. 对每个 属于A的值x,存在一个yB ,使得<x, y>f.
成立时。

在计算机领域函数的精确定义不需要满足第2个条件,其他一样。也就是

fA × B是一个partial函数,只有当

  1. 如果<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

posted on 2007-05-02 23:30 gr8vyguy 阅读(269) 评论(0)  编辑  收藏 所属分类: 计算机科学基础


只有注册用户登录后才能发表评论。


网站导航:
 
<2007年5月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

公告

  • 转载请注明出处.
  • msn: gr8vyguy at live.com
  • 常用链接

    留言簿(9)

    随笔分类(68)

    随笔档案(80)

    文章分类(1)

    My Open Source Projects

    搜索

    积分与排名

    最新评论