從數(shù)學的角度講，程序定義了一函數(shù)，以程序的輸入和程序啟動前的機器狀態(tài)為自變量，以計算輸出為因變量的一個函數(shù)。和數(shù)學中定義的函數(shù)不同的是，程序定義的函數(shù)是不完全的。即是指對某些輸入可能沒有確定的輸出，可能是因為運行程序時出錯(Runtime Error)，也可能是程序無限循環(huán)下去(Nontermination). 所以在計算機領域，探討的函數(shù)是不完全的，是partial的。
函數(shù)在數(shù)學的精確定義是符合兩個條件的關(guān)系，假設A,B為非空集合
f ⊆ A ×
B是一個數(shù)學意義上的函數(shù)，只有當
- 如果<x, y>
? f 并且 <x, z>
? f , 可以推出y=z;
- 對每個 屬于A的值x，存在一個y ? B
,使得<x, y>? f.
成立時。
在計算機領域函數(shù)的精確定義不需要滿足第2個條件，其他一樣。也就是
f ⊆ A ×
B是一個partial函數(shù)，只有當
- 如果<x, y>
? f 并且 <x, z>
? f , 可以推出y=z;
成立時。
也許你對用數(shù)學函數(shù)來表達程序不是很贊同，你可能覺得數(shù)學函數(shù)的對象就是數(shù)字，怎么用數(shù)字來表達鍵盤操作，鼠標點擊，網(wǎng)頁刷新等等東西呢？ 首先函數(shù)的對象可以不是數(shù)字，函數(shù)的定義域和值域可以是任意對象。其次，即是只考慮對象是數(shù)字的函數(shù)，也可以表達所有的程序。即使只是對象是自然數(shù)的函數(shù)，也足夠了。因為象鍵盤操作，網(wǎng)頁刷新等等都可以用數(shù)字來編碼，那么程序只不過讀取一些數(shù)字，修改一些，輸出一些。實際上，如果你拋開鍵盤鼠標顯示器，想像一下計算機的內(nèi)部，就是如此的。換句話說，只考慮計算數(shù)字的程序，并不改變程序的本質(zhì)，并不改變程序到底可以完成什么的能力。
用以上的觀點，我們可以把每個程序，不管是Java的還是什么哇的，等價于一個函數(shù)。
反過來，我們可以把每個函數(shù)等價于一個程序嗎? 也就是說為每個函數(shù)，寫一個程序計算它的關(guān)系。答案是否定。并不是每個函數(shù)都可以計算的，存在不可計算的函數(shù)，比如著名的Halting問題。通俗的講，Halting問題是指判斷任意一個程序是否會在有限的時間里停止。這是不可計算的。如果你能寫出一個程序，用任何一門語言，可以正確判斷所有的Java程序里面是否存在無限循環(huán)。你馬上就轟動世界，拿Turing獎，諾貝爾獎如探囊取物。
Halting問題有多種證明方法，但都是用反證法，假設Halting問題是可以解決的，那么我們可以推出一個謬論。詳情請看有關(guān)可計算理論的書籍。
轉(zhuǎn)載請保留
http://www.aygfsteel.com/xilaile/archive/2007/05/03/115095.html