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