“可計算性(Computability)”是可計算性理論的核心概念，具有深刻的數學內涵和哲學底蘊，圖靈、丘奇、哥德爾等前輩的工作為此概念打下了堅實的基礎，應該說對此概念的理解已經不成問題了，然而從“NP是可計算的”流行觀念看，此概念并未得到人們充分而正確的解讀，這或許是造成千禧年難題“P versus NP”的最根本原因。

我們從回答“什么是可計算性？”說起，來解讀學術界流行觀點的回答，指出“可計算性”蘊含著“機器”與“問題”二個不同的層次：

一，學術界回答“什么是可計算性？”的典型答案

可計算性(calculability)是指一個實際問題是否可以使用計算機來解決。

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.

One goal of computability theory is to determine which problems, or classes of problems, can be solved in each model of computation.

3，Michael Sipser的書“Introduction to the Theory of Computation”

此書是計算理論領域的經典著作，常被大學選為教材。書中干脆就不談“可計算性”，直接用“可計算函數”代替(p. 234)：

COMPUTABLE FUNCTIONS：A Turing machine computes a function by starting with the input to the function on the tape and halting with the output of the function on the tape.

A mathematical problem is computable if it can be solved in principle by a computing device.

二，解讀“可計算性(Computability)”與“可計算的(computable)”

可見，上述回答實際上是在答“什么是可計算問題(computable problem)？”，而不是直接答“什么是可計算性(Computability)？”，那么，我們不禁要問：“computability”與“computable problem”是一回事嗎？

對于“computable problem”的標準答案是由丘奇－圖靈論題給出的(https://en.wikipedia.org/wiki/Church–Turing_thesis)：

J. B. Rosser (1939) addresses the notion of "effective computability" as follows: "Clearly the existence of CC and RC (Church's and Rosser's proofs) presupposes a precise definition of 'effective'. 'Effective method' is here used in the rather special sense of a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps". Thus the adverb-adjective "effective" is used in a sense of "1a: producing a decided, decisive, or desired effect", and "capable of producing a result".

In the following, the words "effectively calculable" will mean "produced by any intuitively 'effective' means whatsoever" and "effectively computable" will mean "produced by a Turing-machine or equivalent mechanical device". Turing's "definitions" given in a footnote in his 1939 Ph.D. thesis Systems of Logic Based on Ordinals, supervised by Church, are virtually the same:

"? We shall use the expression 'computable function' to mean a function calculable by a machine, and let 'effectively calculable' refer to the intuitive idea without particular identification with any one of these definitions."

The thesis can be stated as follows:

Every effectively calculable function is a computable function.[8]

Turing stated it this way:

"It was stated ... that 'a function is effectively calculable if its values can be found by some purely mechanical process.' We may take this literally, understanding that by a purely mechanical process one which could be carried out by a machine. The development ... leads to ... an identification of computability? with effective calculability." (? is the footnote above, ibid.)

“如果一個函數的值能被某個純粹的機械過程求得，那么此函數就是能行可計算的”，可見，“可計算函數”是須要前提的，此前提就是存在著一臺可以求解函數值的機器，換句話說，“可計算性”涉及到“問題”與“機器”二個層次，“機器的能力”為本，“問題的性質”為末。于是，用“可計算問題”代替“可計算性”，實際上是忽略了“可計算性”蘊含的二個層次的關系，從而造成認知混淆，。。。

所以，對于“可計算性”的理解應該回到對“機器的能力”的認知上，即回到對“圖靈機”的認知上來。追本溯源，“圖靈機”是在圖靈1936年那篇重要論文《論可計算數及其在判定問題上的應用》( On Computable Numbers, with an Application to the Entscheidungsproblem)中提出來的，讓我們一起回到這篇具有歷史性意義，但又令人望而生畏，至今使人無法深入的奠基性的論文。

三，《論可計算數及其在判定問題上的應用》中關于“圖靈機”的論述

圖靈在論文中開門見山指出，“按照我的定義，一個數是可計算的，如果它的十進制的表達能被機器寫下來。”就是說，圖靈強調預期的結果一定要被機器寫下來，才能認為一個數是可計算的。

接下來，他開始設計這樣的機器，將之稱為“computing machine”。于“Computing machine”，圖靈又區分了“circular machine”和“circle-free machine”，“circular machine”是因某些因素如“死循環”而無法寫下計算結果的機器；而“circle-free machine”沒有這樣阻礙，能寫下預期結果，換句話說， “circle-free”表達了圖靈稱之的“可計算性(computability)”。

然而，一個問題是否“computable”須要判斷，這就是圖靈這篇奠基性的論文的主題，回答“可計算性的判斷”，進而回答著名的希爾伯特第十問題，。。。

讓我們回到問題：“什么是可計算性？”，相對于流行答案“可計算性是指一個實際問題是否可以使用計算機來解決”，應該說：“可計算性是指算法(圖靈機)具有解決一個實際問題的能力”，“可計算問題是指存在著具有可計算性的算法的問題”。。。

附：

1，圖靈論文“On Computable Numbers, with an Application to the Entscheidungsproblem”原文：https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

2，《論可計算數及其在判定問題上的應用》的前言，第一，二章部分譯文：

“可計算數”簡單說是，其十進制的表達用有限的手段可計算的實數。雖然本文的主題表面上講可計算數，然而幾乎可以同樣容易定義和研究變量為整數或實數或可計算變量的可計算函數，可計算謂詞等。在每種情況下，基本的問題是一樣的，我選擇可計算數來解釋，是因為這樣可以涉及最少的技術細節。不久我希望給出可計算數與可計算函數等之間的關系，這將包括用可計算數表達的實數變量的函數理論。按照我的定義，一個數是可計算的，如果它的十進制的表達能被機器寫下來。

在§9,10，我給出一些論點，想指出可計算數包括所有的能自然看作可計算的數。比如，它們包括代數數的實數部分，Bessel函數的大小的實數部分，PI, e等等。然而可計算數并不包括所有可定義的數。

盡管可計算數類如此之大，在許多方面類似于實數類，它仍然是可枚舉。在§8章，我調查某些證明似乎證明相反的論點。通過正確應用一個論點，可達成一個與哥德爾的結論表面上相似的結論。這些結果可有價值的應用，尤其是，指出(§11)Hilbertian Entscheidungsproblem沒有解。

The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means. Although the subject of this paper is ostensibly the computable numbers, it is almost equally easy to define and investigate computable functions of an integral variable or a real or computable variable, computable predicates, and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the relations of the computable numbers, functions, and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbers. According to my definition, a number is computable if its decimal can be written down by a machine.

In §§ 9, 10 I give some arguments with the intention of showing that the computable numbers include all numbers which could naturally be regarded as computable. In particular, I show that certain large classes of numbers are computable. They include, for instance, the real parts of all algebraic numbers, the real parts of the zeros of the Bessel functions, the numbers X, e, etc. The computable numbers do not, however, include all definable numbers, and an example is given of a definable number which is not computable.

Although the class of computable numbers is so great, and in many ways similar to the class of real numbers, it is nevertheless enumerable. In §8 I examine certain arguments which would seem to prove the contrary. By the correct application of one of these arguments, conclusions are reached which are superficially similar to those of G?del [1] . These results {231} ?have valuable applications. In particular, it is shown (§11) that the Hilbertian Entscheidungsproblem can have no solution.

1，計算機器(Computing machine)

我們已經說過，可計算數是那些可用有限的手段計算而得的表達為十進制的數，這需要較明確的定義。在第九章之前，不對定義作真正合理化的說明，目前我僅說理由是人類的記憶需要限制。

可將一個在計算實數的人與某機器比較，此機器具有有限數目的狀態：q1;q2;…qk(m-格局，m-configurations)。給機器提供一條紙帶(類似紙張)，機器在上面運行，紙帶被分為段(方格，squares)，每個方格上放置一個符號。在任何時刻，只有一個方格，比如第r個方格，放置符號了S(r)，“在機器里”，我們可以稱此方格為“掃描方格”，“掃描方格”里的符號稱為“掃描符號”，“掃描符號”是機器“直接感知”的唯一符號。然而，通過變化格局，機器可以有效記憶已經“見過(掃描)”的符號。機器在任何時刻可能的行為由m－格局qn，掃描符號S(r)決定，這對(qn，S(r))稱為“格局”：于是，格局決定機器可能的行為。在有些格局，掃描方格是空的(即沒有符號)，機器就在掃描方格上寫下一個新的符號；在別的格局，它擦掉掃描符號。機器也可能改變正在掃描的方格，但是僅僅向左右移動一個方格。此外，對任何一個這樣的操作，m－格局可能變化。某些寫下的符號將形成數字序列( sequence of figures)，它是正在計算的表達為十進制的實數，別 的符號只是“輔助記憶”的粗糙紀錄，只有那些粗糙紀錄可能被擦掉。

我的觀點是，這些操作包括了所有用在計算一個數時所需的操作，為此論點辯護要在讀者較熟悉機器理論后才會較容易。在下一節，我將著手發展此理論，假設讀者已經知道“機器”，“紙帶”，“掃描”等。

1. Computing machines.

We have said that the computable numbers are those whose decimals are calculable by finite means. This requires rather more explicit definition. No real attempt will be made to justify the definitions given until we reach §9. For the present I shall only say that the justification lies in the fact that the human memory is necessarily limited.

We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q1, q2, ..., qR which will be called “m-configurations”. The machine is supplied with a “tape”, (the analogue of paper) running through it, and divided into sections (called “squares”) each capable of bearing a “symbol”. At any moment there is just one square, say the r-th, bearing the symbol S(r) which is “in the machine”. We may call this square the “scanned square”. The symbol on the scanned square may be called the “scanned symbol”. The “scanned symbol” is the only one of which the machine is, so to speak, “directly aware”. However, by altering its m-configuration the machine can effectively remember some of the symbols which it has “seen” (scanned) previously. The possible behaviour of the machine at any moment is determined by the m-configuration qn and the scanned symbol S(r). This pair qn, S(r) will be called the “configuration”: thus the configuration determines the possible behaviour of the machine. In some of the configurations in which the scanned square is blank (i.e. bears no symbol) the machine writes down a new symbol on the scanned square: in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or 1eft. In addition to any of these operations the m-configuration may be changed. Some of the symbols written down {232} will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to “assist the memory”. It will only be these rough notes which will be liable to erasure.

It is my contention that these operations include all those which are used in the computation of a number. The defence of this contention will be easier when the theory of the machines is familiar to the reader. In the next section I therefore proceed with the development of the theory and assume that it is understood what is meant by “machine”, “tape”, “scanned”, etc.

2，定義

自動機(Automatic machines)

如果每個階段機器的運動(在第一章的意義上)完全由格局確定，我們稱此機器為?自動機?(a-machine)。

為了某種目的，我們可能使用一些機器(choice machines or c-machines)，它的運動部分由格局決定。當這樣的機器到達一個這樣模棱兩可的格局時，只有當外界的操作做某個任意的選擇，它才能繼續運行。如果我們用機器處理公理系統時會出現這樣的情況，在本文中，我只處理自動機，因此往往忽略前綴a-。

計算機器(Computing machines)

如果一臺機器打印兩類符號，第一類(稱為數字)全是0和1，其它被稱為第二類符號，則機器將被稱為“計算機器”。如果給機器裝置一條空白紙帶，讓它運動起來，從正確的初始m－格局出發，機器打印的第一類符號的子序列稱作“機器計算的序列”；在表達為二進制的十進制實數前放上小數點，稱作“機器計算的數”。

在機器運動的任何階段，掃描方格的數，在紙帶上所有符號的完整序列，及m－格局，被說成是描述那時刻的“完全格局”。機器和紙帶在一系列完整格局之間的變化被稱作“機器的運動”。

循環和非循環機器(Circular and circle-free machines)

如果計算機不再寫下有限數目的第一類符號，被稱作“循環(Circular)”；否則，被稱作“無循環(circle-free)”。

如果一臺機器達到一個格局，從此不再運動，或者即使繼續運動，只能打印第二類符號，而不能打印任何第一類符號，此機器則是“circular”。“circle-free”的意義將在第8章解釋。

可計算序列和可計算數(Computable sequences and numbers)

一個序列被說成“可計算的”，如果能夠通過一臺“circle-free machine”計算而得。一個數是可計算的，如果它與由“circle-free machine”計算的數只差一個整數。

我們應該避免混淆，說可計算序列比說可計算數更經常。

2. Definitions.

Automatic machines.

If at each stage the motion of a machine (in the sense of §1) is completely determined by the configuration, we shall call the machine an “automatic machine” (or a-machine). For some purposes we might use machines (choice machines or c-machines) whose motion is only partially determined by the configuration (hence the use of the word “possible” in §1). When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems. In this paper I deal only with automatic machines, and will therefore often omit the prefix a-.

Computing machines.

If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial m-configuration, the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.

At any stage of the motion of the machine, the number of the scanned square, the complete sequence of all symbols on the tape, and the m-configuration will be said to describe the complete configuration at that stage. The changes of the machine and tape between successive complete configurations will be called the moves of the machine.{233}

Circular and circle-free machines.

If a computing machine never writes down more than a finite number of symbols of the first kind it will be called circular. Otherwise it is said to be circle-free.

A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind. The significance of the term “circular” will be explained in §8.

Computable sequences and numbers.

A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle- free machine.

We shall avoid confusion by speaking more often of computable sequences than of computable numbers.

轉載本文請聯系原作者獲取授權，同時請注明本文來自柳渝科學網博客。

鏈接地址：http://blog.sciencenet.cn/blog-2322490-984797.html

上一篇：丟番圖方程的兩難問題(2)－Entscheidungsproblen

下一篇：智能哲學：計算機是人工智能嗎？－從“圖靈機”到“圖靈檢驗”

總結

以上是生活随笔為你收集整理的1936年发表理想计算机的论文,科学网—图灵1936年论文解读（1）：可计算性 - 柳渝的博文...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。