$\newcommand{\defeq}{\mathrel{\mathop:}=}$

## 2006/09/01

### 等

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 對於科學與藝術的定義也深涉計算理論之核心：

--

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

yen39/02/2006 1:31 pm 說：

Anonymous9/03/2006 5:14 am 說：

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

CS鍋貼也