2006/09/01

有個習性,一件重大或令人興奮的事情將到來時,什麼事情都不想做,只是無謂地消磨時間,空轉等候。現在看起來又進入這個階段了,目標應該是 Introduction to the Theory of Computation, 2/e,再遠一點就是高等微積分、資料結構與演算法等期待甚高的大課程。計算理論(或更精確地說,Turing-computable functions)的適用範圍目前到底有多廣,以及發展得多完善,都是重要的探索方向。一個很重要的問題是,Church-Turing thesis 怎麼猜出成立的?這個假說所導出的哲學議題也相當深刻,摘錄 Wikipedia 對此的簡短說明

The Church–Turing thesis has been alleged to have some profound implications for the philosophy of mind. There are also some important open questions which cover the relationship between the Church–Turing thesis and physics, and the possibility of hypercomputation. When applied to physics, the thesis has several possible meanings:

  • The universe is equivalent to a Turing machine or is weaker; thus, computing non-recursive functions(JK 注:即 non-computable functions)is physically impossible. This has also been termed the strong Church–Turing thesis (not to be confused with the previously mentioned SCTT) and is a foundation of digital physics.
  • The universe is not equivalent to a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a universe in which physics involves real numbers, as opposed to computable reals, might fall into this category.
  • The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it is known that rigorous models such as quantum Turing machines are equivalent to deterministic Turing machines. (They are not necessarily efficiently equivalent; see above.) John Lucas (and more famously, Roger Penrose) have suggested that the human mind might be the result of quantum hypercomputation, although there is no scientific evidence for this proposal.

There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.

Notice that the "real numbers" are mentioned, the foundation on which the entire system of Calculus is built. 最近譯的《視計算機編程為一門藝術》(Computer Programming as an Art)裡面,Knuth 對於科學與藝術的定義也深涉計算理論之核心:

科學是我們透徹理解的知識,透徹到我們能將之教給電腦;而如果我們未完全了解某件事,處理它便是門藝術。既然演算法或電腦程式的概念提供我們一個極為有用的測試,檢測我們對於任何給定主題的知識深度,從藝術到科學的過程就代表我們學會如何令某件事自動化(how to automate something)。

從計算理論到計算機組織(特別是 von Neumann 架構)到高階語言與編譯器,以及另一個大分支 algorithms(and data structures),理路還算明顯,那另外一路呢?從 OOA、OOD,一路下降到 OOP 而觸及高階語言,這一路又是怎麼回事?(目前看來是從心理學、生物學、自然哲學等等發展出來的。)計算機科學所探究的領域與其他科學之間的邏輯聯繫為何?計算機科學本身的架構又是如何?能不能再找出更細緻(delicate; fine-grained)、更泛化(general)、更普遍(universal)、甚至嶄新的結構?

類似問題可以一直問下去。所有問題都還相當模糊,如果能隨著時間愈來愈明確,就有進展了。喔,暫時以直觀看法詮釋「時間」吧,我們畢竟是在人類心智這一抽象層上「思考」呢 :P。

--
有隱約方向總比沒方向好。

Blogger Airman Of Chunghua WIND9/02/2006 8:28 am 說:

後面那段,好像是之前談的電腦AI的部份XD

 
Blogger yen39/02/2006 1:31 pm 說:

已經探討到如此深層的方法了,但是目前還在看懂turing theory中,哈

 
Anonymous Anonymous9/03/2006 5:14 am 說:

http://ac.nccu.edu.tw/~blurryeyes/pf.pdf

CS鍋貼也

 

<< 回到主頁