Читать книгу Lógos and Máthma 2 - Roman Murawski - Страница 23

←52 | 53→

The Status of Church’s Thesis

Co-authored by Jan Woleński

The Church’s Thesis can be simply stated as the following equivalence: (CT) A function is effectively computable if and only if it is partially recursive.30

Thus (CT) identifies the class of effectively computable or calculable (we will treat these two categories as equivalent) functions with the class of partially recursive functions. This means that every element belonging to the former class is also a member of the latter class and reversely. Clearly, (CT) generates an extensional co-extensiveness of effective computability and partial recursivity. Since we have no mathematical tasks, the exact definition of recursive functions and their properties is not relevant here. On the other hand, we want to stress the property of being effective computable, which plays a basic role in philosophical thinking about (CT).31

A useful notion in providing intuitions concerning effectiveness is that of an algorithm. It refers to a completely specified procedure for solving problems of a given type. Important here is that an algorithm does not require creativity, ingenuity or intuition (only the ability to recognize symbols is assumed) and that its application is prescribed in advance and does not depend upon any empirical or random factors. Moreover, this procedure is performable in a finite number of steps. Thus a function f ∶ Nn → N is said to be effectively computable (briefly: computable) if and only if its values can be computed by an algorithm. Putting this in other words: a function f ∶Nn →N is computable if and only if there exists a mechanical method by which for any n-tuple (a1, . . . , an) of arguments, the value f (a1, . . . , an) can be calculated in a finite number of prescribed steps. Three facts should be stressed here: (a) no actual human computability or empirically feasible computability is assumed in (CT); (b) functions are treated extensionally, ←53 | 54→i.e. a function is identified with an appropriate set of ordered pairs; (c) the concept of computability has a modal parameter (“there exists a method”, “a method is possible”) as its inherent feature.

Typical comments about (CT) are as follows:

(i) Church’s thesis is not a mathematical theorem which can be proved or disproved in the exact mathematical sense, for it states the identity of two notions only one of which is mathematically defined while the other is used by mathematicians without exact definition.32 (Kalmár 1959, p. 72)

(ii)While we cannot prove Church’s thesis, since its role is to delimit precisely a hitherto vaguely conceived totality, we require evidence that it cannot conflict with the intuitive notion which is supposed to be complete; i.e. we require evidence that every particular function which our intuitive notion would authenticate as effectively calculable is [...] recursive. The thesis may be considered a hypothesis about the intuitive notion of effective calculability; in the latter case, the evidence is required to give the theory based on the definition the intended significance. (Kleene 1952, pp. 318–319), Kleene 1967, p. 232)

(iii) This is a thesis rather than a theorem, in as much as it proposes to identify a somewhat intuitive concept phrased in exact mathematical terms, and thus is not susceptible of proof. But very strong evidence was adduced by Church, and subsequently by others, in support of the thesis.

It [(CT) – and other similar characterizations – our remark, R.M. and J.W.] must be accepted or rejected on grounds that are, in large part, empirical. [...]. Church’s Thesis may be viewed as a proposal as well as a claim, that we agree henceforth to supply previously intuitive terms (e.g., “function computable by algorithm”) with certain precise meaning. (Rogers 1967, p. 20)

These three quotations shed some light on several problems raised by (CT). Firstly, we can and should ask for evidence for it. We take the standard position that the implication from recursivity to computability (every recursive function is computable) is obvious and the opposite implication from computability to mathematical definition of effective calculability, i.e., recursivity (every computable function is recursive), has a sufficient justification.33 Secondly, one can ask for the fate of (CT) in some logical framework, in particular, in intuitionistic or constructive systems (see Kleene 1952, pp. 318, 509–516, Kreisel 1970,McCarty 1987), but we ←54 | 55→entirely neglect this question.34Thirdly, there are various special problems, mostly philosophical, we believe, related to (CT). Does this thesis support mechanism in the philosophy of mind or not (see Webb 1980)? How is it related to structuralism in the philosophy of mathematics (see Shapiro 1983)? We also neglect this variety of questions, except eventual parenthetical remarks aimed at exemplification. Fourthly, and this is our main concern in this paper, there arises the problem of the status of (CT). We split this topic into two subproblems. (CT) can be considered from the point of view of its function in mathematical language or various conceptual schemes. The second subproblem focuses on the character of (CT) as a statement or sentence. To be more specific, we note that one of the views considers (CT) as a definition. This gives an illustration of the former subproblem. However, independently whether (CT) has the status of a definition or not, it is captured by a sentence. Now, we can ask whether this sentence is analytic or synthetic, a priori or a posteriori .This provides an illustration of the latter subproblem. Although both subproblems are closely related, their separation, even relative, makes the analysis of the status of (CT) easier.

The following views about the function of (CT) can be distinguished :35

(A)	(CT) is an empirical hypothesis,
(B)	(CT) is an axiom or theorem,
(C)	(CT) is a definition and
( D)	(CT) is an explication.

Ad. (A) (CT) can be considered as referring to human (possibly idealized) abilities. Hence Church’s Thesis is connected with questions concerning relations between mathematics and material or psychic reality. The last view is represented by Post, who regarded the notion of computability as a notion of a psychological nature (Post 1965, pp. 408, 419; page-reference to the first edition):

[...] for full generality a complete analysis would have to be made of all the possible ways in which the human mind could set up finite processes for generating sequences. [...] we have to do with a certain activity of the human mind as situated in the universe. As activity, this logico-mathematical process has certain temporal properties; as situated in the universe it has certain spatial properties.

Post maintained that (CT) should be interpreted as a natural law and insisted on its empirical confirmation (similarly DeLong 1970, p. 195). However, one should be very careful with such claims. In fact, we have no general and commonly accepted psychological theory of human mental activities, even as far as the matter concerns ←55 | 56→the scope of computation. Hence, it is very difficult to think about (CT) as an empirical hypothesis about the human mind and its abilities. Eventually (CT) can be considered as related to mechanism in the philosophy of mind (see above) and even as confirming this view. Although we do not deny that (CT) has an application in philosophy, we do not think that this thesis as a tool for a philosophical analysis of the mind body problem functions as a genuine empirical hypothesis. We think that the use of (CT) for supporting mechanism in the philosophy of mind is very similar to deriving (or not) indeterminism from the principle of indeterminacy. We have to abstain from further remarks concerning this interpretation of (CT), because it would require a longer metaphilosophical discussion.

Ad. (B) One should distinguish two understandings of axioms or theorems. Firstly, axioms can be considered as principal metatheoretical assumptions. When Kreisel (1970) considers (CT) as a kind of reducibility axiom for constructive mathematics, he uses the concept of axiom in this sense. Yet, we are inclined to think that his comparison of (CT) with “hypothesis” ofV = L in set theory is rather misleading. In the case of V = L, there is no need to use quotes and say “hypothesis”, because we have to do with a set-theoretical axiom, whereas Kreisel’s analysis does not result in an axiomatic system of set theory. This leads to the second use of the term "axiom", referring to an element of an axiomatic system. A similar problem arises with respect to the category of being a theorem. Mendelson (1990, p. 230) writes: