第一章　可計算性函數

§1.1　算法和能行過程的直觀含義（非數學定義）

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

+，-，×，÷是最簡單的算法和能行過程.算法也叫能行方法或能行過程，是一個相當古老的概念，其歷史最早可以上溯到古希臘時代.

中國的祖沖之計算圓周率的算法也必定是能行的，他的算法記錄在《綴術》中，可惜失傳了.現在保存完整的《九章算術》，是中國古代第一部數學專著，大概成書于公元一世紀.《九章算術》專注于講解算法，不注重推理證明.一般是先提出幾個同類型的具體的問題，然后給出結果，給出計算過程.舉個例子，開平方運算在《九章算術》是這樣運算的：

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

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

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

（2）計算=75-64=11；

（3）再計算=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.

從《九章算術》的這個例子我們可以看出，這些是自動運行的方法，它們可以機械運行.因此我們可以得到結論：在直覺上，算法或能行方法，就是一種機械規則，或是一種自動運行的方法，或是一種能執行某種數學運算的程序.我們在中小學學過的所有數學運算其實都是能行運算的，簡稱能行的，例如求第n個質數、求兩個正整數x，y的最大公因數、判斷是否x|y……在德國海德堡的一個博物館里，有一臺世界上最早的計算機.輸入一個數字，它會自動地輸出另一個數字.這是算法的另外一個特點，即算法可以用黑箱非正式表示.輸入一個物體，如一個數字，通過黑箱（如一臺電腦，或一條被馴服的狗），自動地給出一個輸出.

上面這些函數在直覺上都是可計算的.我們一般認為一個函數稱為可計算函數，如果存在一種算法能夠計算該函數.當然并非所有函數均為可計算函數.例如

就是直覺上不可計算函數.我們不可能在事先知道g（n）=0，除非我們在一位位查看π的小數表示形式時恰好發現存在連續n個7.我們不知道對某個n，我們會不會不得不一直找尋下去.所以從直覺上看g不可計算．所以，可計算的事物，必有一個算法，必定能在有窮步內給出答案.