從數學的角度講，程序定義了一函數，以程序的輸入和程序啟動前的機器狀態為自變量，以計算輸出為因變量的一個函數。和數學中定義的函數不同的是，程序定義的函數是不完全的。即是指對某些輸入可能沒有確定的輸出，可能是因為運行程序時出錯(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.aygfsteel.com/xilaile/archive/2007/05/03/115095.html