第一章　可計(jì)算性函數(shù)

§1.1　算法和能行過(guò)程的直觀含義（非數(shù)學(xué)定義）

計(jì)算機(jī)的主要功能就是能算，首要關(guān)心的就是能不能算、如何算.能算，就表明能獲得信息，以某種方式獲得信息.算法就是獲得信息的過(guò)程.那么什么是算法呢？什么是能行過(guò)程？

+，-，×，÷是最簡(jiǎn)單的算法和能行過(guò)程.算法也叫能行方法或能行過(guò)程，是一個(gè)相當(dāng)古老的概念，其歷史最早可以上溯到古希臘時(shí)代.

中國(guó)的祖沖之計(jì)算圓周率的算法也必定是能行的，他的算法記錄在《綴術(shù)》中，可惜失傳了.現(xiàn)在保存完整的《九章算術(shù)》，是中國(guó)古代第一部數(shù)學(xué)專(zhuān)著，大概成書(shū)于公元一世紀(jì).《九章算術(shù)》專(zhuān)注于講解算法，不注重推理證明.一般是先提出幾個(gè)同類(lèi)型的具體的問(wèn)題，然后給出結(jié)果，給出計(jì)算過(guò)程.舉個(gè)例子，開(kāi)平方運(yùn)算在《九章算術(shù)》是這樣運(yùn)算的：

開(kāi)方術(shù)曰：“置積為實(shí)，借一算，步之，超一等.議所得，以一乘所借一算為法而以除.除已，倍法為定法.其復(fù)除，折法而下.復(fù)置借算步之如初.以復(fù)議一乘之，所得副，以加定法，以除.以所得副從定法，復(fù)除折下如前.”

例1.1.1　n=7569，求.其算法如下：

（1）可將n分解為n=n1+100n2，即7569=69+75×100，則整數(shù)平方根可分解為s=s1+10s2，余數(shù)為r=n-s2；

（2）計(jì)算=75-64=11；

（3）再計(jì)算=7，r1=（100r2+n1）-（20s2+s1）s1=（11×100+69）-（20×8+7）×7=1169-1169=0；

（4）得s=s1+10s2=87，r=0.即7659=872+0.

從《九章算術(shù)》的這個(gè)例子我們可以看出，這些是自動(dòng)運(yùn)行的方法，它們可以機(jī)械運(yùn)行.因此我們可以得到結(jié)論：在直覺(jué)上，算法或能行方法，就是一種機(jī)械規(guī)則，或是一種自動(dòng)運(yùn)行的方法，或是一種能執(zhí)行某種數(shù)學(xué)運(yùn)算的程序.我們?cè)谥行W(xué)學(xué)過(guò)的所有數(shù)學(xué)運(yùn)算其實(shí)都是能行運(yùn)算的，簡(jiǎn)稱(chēng)能行的，例如求第n個(gè)質(zhì)數(shù)、求兩個(gè)正整數(shù)x，y的最大公因數(shù)、判斷是否x|y……在德國(guó)海德堡的一個(gè)博物館里，有一臺(tái)世界上最早的計(jì)算機(jī).輸入一個(gè)數(shù)字，它會(huì)自動(dòng)地輸出另一個(gè)數(shù)字.這是算法的另外一個(gè)特點(diǎn)，即算法可以用黑箱非正式表示.輸入一個(gè)物體，如一個(gè)數(shù)字，通過(guò)黑箱（如一臺(tái)電腦，或一條被馴服的狗），自動(dòng)地給出一個(gè)輸出.

上面這些函數(shù)在直覺(jué)上都是可計(jì)算的.我們一般認(rèn)為一個(gè)函數(shù)稱(chēng)為可計(jì)算函數(shù)，如果存在一種算法能夠計(jì)算該函數(shù).當(dāng)然并非所有函數(shù)均為可計(jì)算函數(shù).例如

就是直覺(jué)上不可計(jì)算函數(shù).我們不可能在事先知道g（n）=0，除非我們?cè)谝晃晃徊榭处械男?shù)表示形式時(shí)恰好發(fā)現(xiàn)存在連續(xù)n個(gè)7.我們不知道對(duì)某個(gè)n，我們會(huì)不會(huì)不得不一直找尋下去.所以從直覺(jué)上看g不可計(jì)算．所以，可計(jì)算的事物，必有一個(gè)算法，必定能在有窮步內(nèi)給出答案.