从数学的角度讲，程序定义了一函数，以程序的输入和程序启动前的机器状态为自变量，以计算输出为因变量的一个函数。和数学中定义的函数不同的是，程序定义的函数是不完全的。即是指对某些输入可能没有确定的输出，可能是因为运行程序时出错(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