图灵谁如何定义“可计算性”的？

 I. How did Turing define the computability?

Turing's 1936 paper, as its title suggests: On Computable Numbers, with an Application to the Entscheidungsproblem, aimed to solve the Entscheidungsproblem proposed by Hilbert based on computable numbers.

 

Turing answered the Entscheidungsproblem negatively, Turing said:

I propose, therefore, to show that there can be no general process for determining whether a given formula A of the functional calculus K is provable (Note: K refers to the first-order predicate), i.e. that there can be no machine which, supplied with any one A of these formulae, will eventually say whether A is provable.

Therefore, Turing gave a definition of decision problem such that « there is a general process for determining . . . ».

 

1. Decision problem 

 

Turing said ([1], Section 8):

The expression ''there is a general process for determining . . .'' has been used throughout this section as equivalent to ''there is a machine which will determine . . .''. This usage can be justified if and only if we can justify our definition of "computable''. For each of these ''general process'' problems can be expressed as a problem concerning a general process for determining whether a given integer n has a property G(n) [e.g. G(n) might mean ''n is satisfactory'' or ''n is the Godel representation of a provable formula''], and this is equivalent to computing a number whose n-th figure is 1 if G(n) is true and 0 if it is false.

 

In order to define the concept of "computable'', Turing proposed the computing machine, i.e., today's Turing Machine, constructively expressed a general process, and expressed the computing result by a computing machine as computable number. Attention: The computing result here is not for one instance, but for all instances of a problem.

 

2. The figure of computability : computable number

 

Turing said ([1], Section 1):

According to my definition, a number is computable if its decimal can be written down by a machine.

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 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 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.

It can be seen that the computable number is an intuitive expression of circle-free machine. In this sense, it can be said that the computable number is an image of the computability of Turing machine, which illustrates the holistic and infinite nature of computability.

 

II. The disappearance of computable number from the current theory of computation

 

The computable number is the guiding line throughout Turing's 1936 paper (On Computable Numbers, with an Application to the Entscheidungsproblem), as Charles Petzold said in his book The Annotated Turing [4]:

Although the Entscheidungsproblem was certainly the motivation for Turing's paper, the bulk of the paper itself is really about computable numbers. In Turing's definition, these are numbers that can be calculated by a machine. Turing's exploration of computable numbers accounts for the first 60 percent of the paper.

 

However, the computable number has disappeared from the current theory of computation! On the other hand, Turing machine has been adopted and developed to make computer science what it is today. 

 

So, why did the computable number disappear? How did it disappear?

 

Let us take the example of Collatz's conjecture [5] for a preliminary discussion of this topic.

 

Collatz's conjecture is that for every positive integer, if it is odd, multiply it by 3 and add 1, if it is even, divide it by 2, and so on, to eventually get 1.

 

Collatz's sequence can be expressed as a recursive function f(n):

f(n) = 1 (n=1)

f(n) = f(n/2) (n is pair)

f(n) = f(3n+1) (n is impair)

 

The real meaning of Collatz's conjecture is a conjecture about the computability of Turing machine corresponding to the recursive function f(n).

 

Now, let's look at Collatz's conjecture from the perspective of the halting problem and Turing's decision problem:

 

1. The perspective of Turing's decision problem 

 

Collatz's conjecture: determine whether the Turing machine corresponding to the recursive function f(n) eventually gets 1 for any given positive integer n? i.e. is the Turing machine circle-free, writing down a computable number : f(1)f(2)f(3)f(4)f(5)f(6)... = 111111...?

2. The perspective of the halting problem

 

Collatz's conjecture: determine whether the Turing machine corresponding to the recursive function f(n) halts for any given positive integer n?

 

From the point of view of the halting problem, it is to determine whether Collatz's conjecture holds by enumerating individuals, but the computability of f(n) is holistic and infinite in nature, so it cannot be achieved by enumeration. In fact, by 2020, the positive integers have been verified up to 2^68, and no exceptions have been found, but this does not prove that the conjecture holds for any size of number.

 

From the point of view of Turing's decision problem, it is hoped, by digging deeper into the properties of the integers, to determine whether the Collatz conjecture holds for the integers as a whole.

Then we can see that, it is in the definition of halting problem that the computable number has been eliminated, which leads to the disappearance of the determination of computability of Turing machine, the disappearance of the determination of validity of proof from the perspective of proof.

 

Perhaps we can see that «  a butterfly tapping its wings in Brazil can cause a tornado in Texas a month later »,…

Reference :

[1] Turing, A. M. (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". 

https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

[2] Martin Davis (1958). Computability and Unsolvability. New York: McGraw-Hill.

[3] B. Jack. Copeland, The EssentialTuring, 2004.

http://www.cse.chalmers.se/~aikmitr/papers/Turing.pdf

[4] Perzold Charles, The Annotated Turing - A Guided Tour Through Alan Turing's Historic Paper On Computability And The Turing Machine

https://github.com/pengbo-learn/books/blob/master/The%20Annotated%20Turing%20(Petzold-2008).pdf

[5] https://en.wikipedia.org/wiki/Collatz_conjecture