本書讓我知道的是，計算機并不能解決所有問題。
“圖靈把這個信條貫徹到了極致。老實說，我一開始對他的做法還挺惱火的。每次他給我布置一個任務，我完成以后，他都不肯賞臉看一看我的解法，而是會自己先解一遍；只有自己先初步嘗試一遍之后，才會看我的解法。我很快就看到了他這樣做的好處。首先，他如果不親自嘗試，是不會輕易接受別人的想法的，不過更重要的是，他經常會想出一些具有獨創性的方法。這些方法我可能想都沒有想過，而且他要是一開始就看我的解法，也不一定想得出來。”
有一位理發師，他只為不給自己刮臉的人刮臉。那么他給不給自己刮臉呢？ 如果他不給自己刮臉，他就屬于“不給自己刮臉的人”，他就要給自己刮臉，而如果他給自己刮臉呢？他又屬于“給自己刮臉的人”，他就不該給自己刮臉。唯一說得通的解釋是，他既給自己刮臉，又不給自己刮臉——但這在邏輯上是不可能的。所以說這是一個悖論。
當時的機器只能做一件事情，那就是它們被設計出來做的事情。但是希爾伯特提出的挑戰是制造一臺萬能機，這臺機器必須通曉任何數學語言，能夠看懂人們用數學語言表述出來的任何命題。要做到這一點，它必須能夠按照任何順序進行任何可能的數學運算，從而給操作者留出充分的余地改變問題
圖靈認為，要想判斷他的機器會不會停機，那就需要再構造一臺圖靈機，以對第一臺機器進行檢測，因為他知道，他假想的機器在理論上可以進行任何數學運算。于是他假想出第二臺圖靈機，如果檢測到第一臺圖靈機永不停機，那么第二臺機器就會停機，然后輸出“不停機”；如果檢測到第一臺圖靈機停了機，那么第二臺機器就會一直運轉下去。 現在，腦筋急轉彎的地方來了。假如第二臺機器反觀自身，判斷自己會不會停止計算，那會發生什么情況？圖靈對此進行了設想，他突然發現了一個悖論：如果機器檢測到自己會永不停機，那么它就會停機，然后輸出“不停機”；如果機器檢測到自己停了機，那么它就會一直運轉下去。這在邏輯上是不可能的，由此證明，有些圖靈機是不可判定的——我們永遠也無法判斷它們會不會停機。 盡管這樣說或許令人費解、甚至不可思議，但是不可判定或不可計算的問題的確大量存在——自此之后，這樣的事實一直讓計算機程序員備受困擾。圖靈的研究結果表明，有些數學問題是計算機無法解決的，這與計算機的運算能力、運算速度和內存容量無關。
邱奇連吃早飯的方式都很有邏輯：“先把牛奶倒進空碗里，放適量的糖，用早餐勺攪拌均勻，然后放一兩勺麥片。吃完這點麥片后，再接著放一兩勺，邊吃邊放。這樣一來，糖就會在牛奶中充分溶解，分布均勻，而且麥片也不會泡得太軟。”
理論計算機科學家羅賓·赫希（Robin Hirsch）研究了這些思想。“這個世界上存在三種類型的事物，”他說，“第一種在理論上可能做到，但卻無法解決；第二種在實際上可能做到（因此在理論上也必定可能做到）；第三種在理論上可能做到，但在實際上卻未必可能做到——雖然說是在理論上可能做到，但往往是比較匪夷所思的類型，即使宇宙的壽命終結也不一定能夠完成，所以從實際角度講，我們也解決不了。在計算機科學領域，大多數有趣的問題都屬于這個范疇。”
在計算機科學領域，我們常用的詞是“算法”，而不是“方法”。這個術語主要用于描述我們打算寫入計算機程序的方法或過程，它給出了程序運行的所有步驟。因此，所謂排序算法，就是指為一系列事物排序的方法。
文章列表
留言列表
