Epistemological Meaning of Church-Turing Thesis in Mathematics Philosophy

Patrice Pissavin (patrice_pissavin@orange.fr) HEPIC seminar 11/03/2021 1

The context is of logic and mathematicss philosophy and not of computer s philosophy So, we refer to the standard Church-Turing thesis and to the standard Turing machine, that is to say as introduced by the forerunner (Church, Kleene, Post and Turing) in 1936, as part of the first order predicate calculus decidability question (Entscheidungsproblem) Our subject is then both philosophical and historical, referring in particular to a debate that took place until the sixties, which opposed classical mathematics to intuitionism mathematics (in Brouwer s sens), under the shadow of Hilbert and is program 11/03/2021 2

1. The epistemological meaning of expressing the intersubjectivity of a formal proof in mathematics may be associated with the use of the Turing machine 2. A metamathematic proof of decidability (in Hilbert s sens), based on the the Church-Turing thesis, does not fully respect the requirement of intersubjectivity required for a mathematical proof 3. We cannot go beyond the standard Turing machine, therefore of the standard Church-Turing thesis, while retaining the epistemological significance that may be associated with the use of the Turing machine 11/03/2021 3

Proposal of three criteria to guarantee the epistemological requirement of intersubjectivit for a mathematical result: 1) The proof must be publicly communicable in a finite time 2) Its checking should not appeal to intuition or intelligence in any way, nor to any commitment that cannot be verified in principle and in particular to no ontological commitment (typically in favor of a kind of realism) in mathematics 3) This checking must also be publicly communicable in a finite time 11/03/2021 4

The introduction of a finite and mechanical procedure, which characterizes a calculation on natural numbers, is the most efficient way that has been found by human beings up to date to best meet the intersubjectivity requirement expected from a mathematical result The assertion that the values of a function are everythere calculable in a finite number of steps has meaning only under the condition that this calculation does not depend on some individual arbitrariness, but constitutes a procedure capable of being repeated and communicated to other people at any time. Hence it must be a mechanical procedure, [ ]. [P ter 1957 (1967), p. 225; underlined by us] Turing arguably did not mention such a hypothesis in his seminal paper, but one can reasonably think that such an idea was implicit (and obvious) for him in the case of the exclusive use of paper and pencil 11/03/2021 5

Turing explains the limitations of the calculating human agent he considers to justify the constraints he imposes to the "Turing machine" [Sieg 2002, p. 395-397]: 1) boundedness condition; there is a fixed bound on the number of configurations a human computeur can immedialely recognize; 2) locality condition; a human computer can change only immediately recognizable sub-configurations. The "Turing machine" is therefore neither an abstract digital machine (in the broad sense) nor an idealized human being (in the broad sense), but an abstract digital machine characterizing the behavior of an idealized human being when he routinely calculates (in 1936 the english word "computer" used byTuring, could not mean anything other than: human calculator) 11/03/2021 6

The constraints applied to the Turing machine are technically equivalent to the usual effectiveness constraints applied to a formal system, which are reflected in particular by the recursively enumerable character of the set of theorems [Sieg 2006, p. 194-195] The use of a formal proof by means of an effective formal system to perform the checking of an informal mathematical proof, appears to be the best solution to ensure the requirement of intersubjectivity I argued that the sharpenig of axiomatic theories to formal ones was motivated by epistemological concerns. A central point was the requirement that the checking of proofs ought to be done in a radically intersubjective way; it should involve only operations similar to those used by a computor [human computer] when carrying out an arithmetic calculation. [Sieg 1994, p. 101; the comment in square brackets is our; underlined by us] 11/03/2021 7

The Church-Turing thesis was introduced in 1936 with the objective of giving precise technical content to the metamathematic notion of decidability: 1) Any effectively (intuitively) computable function is a total general recursive function (or Turing computable which ends) 2) Any total general recursive function is effectively (intuitively) computable (converse) Its formulation allowed Church in 1936 and Turing in 1936-1937 to establish the indecidability of the calculus of first order predicates, in answer to the Entscheidungsproblem 11/03/2021 8

Consider the following integer function proposed by Elliott Mendelson in 1990: f(i) = 1 if the Goldbach s conjecture is true and f(i) = 0 if the Goldbach s conjecture is false Such a function can undoubtedly be considered to be total general recursive (in an absolute sense) while it is rejected by intuitionists (Brouwer and his successors), lack of a procedure to calculate it Respecting the requirement of intersubjectivity thus amounts to asking for a circumscription, among the total general recursive functions, between those whose demonstration of the general recursive character is constructive and the others 11/03/2021 9

This question, which raises the problem of the acceptance of the Church-Turing thesis converse by intuitionists, was raised by Church and Kleene in their seminal papers: The reader may object that this algorithm cannot be held to provide an effective calculation of the required particular value of [the function] Fi unless the proof is constructive that the required equation fnii(k1i, k2i, knii) = ki will ultimately be found. But if so this merely means that he should take the existential quantifier which appears in our definition of a set of recursion equations in a constructive sens. What the criterium of constructiveness shall be is left to the reader. [Church 1936, p. 351, n. 10; the comment in square brackets is our; underlined by us] The definition of [total] g n ral recursive function offers no constructive process for determining when a recursive function is defined. [Kleene 1936, p. 738; the comment in square brackets is our] 11/03/2021 10

In 1952, in his reference book, Kleene took literally the undoubtedly somewhat casual remark of Church that we have just quoted, without giving any criterion of the effectiveness of a proof: In other words, we should not claim that a function is effectively calculable on the ground that it has been shown to be general recursive, unless the demonstration that it is general recursive is effective. [Kleene Stephen, 1952 (2009), p. 319; the comment in square brackets is our] In 1958, Arend Heyting underlines that an intuitive notion of effectiveness is necessary in order to be able to respond to Kleene's request from 1952 that we have just cited [Heyting 1958, p. 106] In 1959 R zsa P ter, who also defends the need for a constructivist restriction of the total general recursive functions that characterize the Church-Turing thesis, argues that it is impossible to define it without falling into a vicious circle [mentioned in Heyting 1959, p. 70] In 1967 Kleene returned to the subject while contenting himself with asserting that it suffices to admit that the premise is recognized as constructive, which does not shed much light [Kleene 1967 (1971), p. 249, n. 171] 11/03/2021 11

The only acceptable solution from an intuitionist point of view would be to state a primitive and consensual notion of constructive proof, but a solution universally accepted by intuitionists has not yet been reached [Sundholm 2014, p. 14-28] The conclusion that can be drawn from this analysis is therefore that no satisfactory solution has appeared to meet the requirement of intersubjectivity in the case of a metamathematic proof of decidability, directly associated with the Church-Turing thesis This explains why the Church-Turing thesis is generally taken in the classical sense (without restriction of the field of total general functions). In any case, it is on such a basis that the classic results of undecidability have been obtained: theorems of Church of 1936 and of Turing of 1936-1937 The consequence is then that a metamathematic proof of decidability does not completely respect the requirement of intersubjectivity required for a mathematical proof 11/03/2021 12

Numerous and varied mathematical and computational solutions have been proposed with the aim of going beyond the (standard) Church-Turing thesis, which in fact involves going beyond the (standard) Turing machine The question then arises to know to what extent these proposals for going beyond the Turing machine respect the requirement of intersubjectivity applied to a formal proof in mathematics, of which the use of the Turing machine can be considered as an expression The most eliminatory criterion is undoubtedly the need for the proof and its checking (more generally the execution of a calculation) to be publicly available (in a finite time). The Turing machine is potentially affected by this criterion at three levels: its inputs, its operation and its outputs 11/03/2021 13

The inputs to the Turing machine cannot be infinite, neither a priori nor random (response to an objection by Robert Soare [Soare 1996, p. 286] and to a question by Oron Shagrir [Shagrir 2006, p. 409-411]) Also eliminated on the basis of this criterion are Hava Siegelmann's neural network solutions analyzed by Martin Davis, which turn out to be non-computable because their input parameters are [Davis 2004, p. 202-203] The same is true of the Turing machine coupled to an open environment: with [P gny 2013, p. 126], against [Copeland, Sylvan 1999, p. 51] 11/03/2021 14

The operation of the Turing machine cannot involve either infinity in action or randomness This restriction applies in the first place to the modified "Turing machine", studied by Turing himself as an "oracle machine (or "O-machine") in [Turing 1939]. Indeed, even if the approach proceeds step by step, the explanation provided by Turing does not contain any information on the procedure that would allow the oracle to be calculated Interactive calculations " la Wegner and Golding" discussed by Ma l P gny, which involve a potentially different algorithm for each instance are also eliminated [P gny 2013, p. 120] It is a fortiori the same for the call for a possible "non- numerical computability" suggested by [Soare 1996, p. 294] and [Copeland 2000, p. 32] 11/03/2021 15

The outputs of the Turing machine cannot be infinite This applies to the objection of the "calculator prodigy" introduced by Michael Rescorla [Rescorla 2007, p. 262] and by Ma l P gny [P gny 2013, p. 67, n. 18]. Any result (or succession of results) proposed as a calculation will however be recognized as such by the community of mathematicians, only if it is possible to come back to it (at least in principle) by means of an approach " la Turing 1936-1937", otherwise this result will only be considered as a prophecy (or an oracle) 11/03/2021 16

None of the solutions that have been proposed as going beyond the standard Turing machine succeeds to meet the criteria associated with the requirement of intersubjectivity applied to a formal proof in mathematics This result is not fortuitous but stems fundamentally from the link between the unrestricted use of the standard Turing machine and the usual efficiency criteria applied to a formal system. A possible going beyond the standard Turing machine would indeed imply a broadening of these criteria of effectiveness, knowing that no serious solution in this direction has been proposed for eighty years Of course, this observation does not remove the potential interest of extensions of the Turing machine and of the Church-Turing thesis with other purposes, but it prevents these extensions from retaining the epistemological benefit linked to the intersubjectivity given by the standard version ("to have your cake or to eat it") 11/03/2021 17

The use of the Turing machine can be considered as an expression of the epistemological requirement of intersubjectivity required for the checking of an informal mathematical proof, when this is carried out by means of a formal proof It is impossible to fully ensure the intersubjectivity requirement expected from a mathematical result in the case of a (metamathematic) decidability proof (for lack of being able to apply this criterion to the set of recursive functions general values taken into account in the classical expression of the Church-Turing thesis) None of the solutions that have been proposed in favor of going beyond the Church-Turing thesis, succeeds to meet all the criteria associated with the requirement of intersubjectivity of a formal proof, for which the use of the (standard) Turing machine can be considered as an expression 11/03/2021 18

Church Alonzo 1936 "An Unsolvable Problem of Elementary Number Theory ", American Journal of Mathematics, n 58, p. 345-363. Copeland Jack 2000 "Narrow versus wide mechanism : including a re-examination of Turing's views on the mind- machine issue", The Journal of Philosophy, vol. 97, n 01, p. 5-32. Copeland Jack, Sylvan Richard 1999 "Beyond the universal Turing machine ", Australasian Journal of Philosophy, vol. 77, n 1, p. 46-66. Davis Martin 2004 "The myth of hypercomputation" in Teuscher Christof (ed.), Alan Turing: life and legacy of a great thinker, Berlin, Springer, p. 195-211. Heyting Arend 1958 "Intuitionism in mathematics" in Klibansky Raymond (ed.), La philosophie au milieu du vingti me si cle (Philosophy in the mid-century: a survey, Vol. 1: Logique et philosophie des sciences (Logic and philosophy of science), Firenze, La Nuova, p. 101-115; 1959 "Some remarks on intuitionism" in Heyting Arend (ed.), Colloquium: Constructivity in Mathematics, Amsterdam, North Holland, p. 69-71. 11/03/2021 19

Hilbert David, Bernays Paul 1939 (2001) Fondements des math matiques. 2, 2nd edition (1970), Fr. trans. Fran ois Gaillard, Eug ne Guillaume, Marcel Guillaume, Paris, L Harmattan. Kleene Stephen 1936 "General recursive functions of natural numbers", Mathematische Annalen, vol. 112, p. 727-742; 1952 (2009) Introduction to meta-mathematics, New-York, Iski Press; 1967 (1971) Logique math matique, Fr. trans. Jean Largeault, Paris, Librairie Armand Colin. P gny Ma l 2013 "Sur les limites empiriques du calcul", Th se de l'Universit Paris I. Peters R zsa 1957 (1967) Recursive functions, 2ndedition (1959), Eng. trans. Istvan F ldes, New York, Academic Press. Rescorla Michael 2007 "Church's Thesis and the conceptual analysis of computability", Notre Dame Journal of Formal Logic, vol. 48, n 2, p. 253-280. Shagrir Oron 2006 "G del on Turing on computability" in Olszewski Adam, Wolenski Jan, Janusz Robert (ed.), Church Thesis after 70 years, Frankfurt, Ontos-Verlag, p. 393-419. 11/03/2021 20

Sieg Wilfried 1994 "Mechanical procedures and mathematical experience" in Alexander George (ed.), Mathematics and mind, Oxford, Oxford University Press, p. 71-117; 2002 "Calculations by man and machine: conceptual analysis" in Sieg Wilfried, Sommer Y., Talcott C. (ed.), Reflections on the Foundations of Mathematics; Essays in Honor of Solomon Feferman, Urbana, A. K. Peters, p. 390-409; 2006 "G del on Computability", Philosophia Mathematica, n 14, vol. 2, p. 189-207. Soare Robert 1996 "Computability and recursion", The Bulletin of Symbolic Logic, vol. 2, n 3, p. 284-321. Sundholm G ran 2014 "Constructive recursive functions, Church's thesis, and Brouwer's theory of the creating subject: afterthoughts on a parisian joint session" in Dubucs Jacques, Bourdeau Michel (ed.), Constructivity and computability in historical and philosophical perspective, Dordrecht, Springer, p. 1-35. Turing Alan 1936-1937 (1995) "Th orie des nombres calculables, suivie d'une application au probl me de la d cision", Fr. trans. Julien Basch, in La Machine de Turing, Paris, Seuil, p. 47-104; 1939 (1965) "Systems of logic based on ordinals" in Davis Martin (ed.), The undecidable, Hewlett, Raven Press, p. 155-222. 11/03/2021 21