§1. Dr. Paula Quinon has kindly shared with me the abstract of her recent work, titled “What “computing” means?” (see item 6 in References), and added some comments to more accurately explain her key ideas. Among the comments there was a link to S.Feferman’s paper “Turing’s ‘Oracle’. From Absolute to Relative computability and Back.” (2016).
In that paper I find a passage which seems to me crucial from an epistemological point of view, though it does not contain any direct references to philosophy. Before I quote and comment on it, let me express my personal attitude to some issues investigated by Ms. Quinon, and how I see their relation to the passage in question.
Frankly speaking, I am no expert in the issues of computing, and my interest in them is rather, so to say, old-fashioned, going back to Kazimierz Ajdukiewicz’s project in the early 1960s, concerned with the justification of statements and decisions. The subject was discussed at the very impressive international conference in 1961, chaired by Ajdukiewicz, and at a Polish conference, meant like a general rehearsal of Polish participants before that important international meeting.
What I remember best from those events, it is Andrzej Grzegorczyk discussion on the intuitive reasons of accepting axioms in mathematical theories. How such intuitions might be scientifcally justified? This issue seemed then like a puzzle which nobody was ready to solve in the situation (in philosophy of logic and mathematics) at that time. Let us call it
Ajdukiewicz-Grzegorczyk problem.
According to my knowledge, only Hao Wang’s publications in the nineteen-nineties, born from his penetrative discussions with Gödel, are likely to shed some light at the methodological problem of justifying axioms. They are related to the distinction between absolute and relative solvability as considered by Feferman.
Let the fact of adding a new axiom to a theory be exemplified by the transition from arithmetic without the Axiom of Complete Induction — ACI (like, e.g., Presburger arithmetic) to the theory enriched with this axiom. This results in an enormous amplification of the scope of solvability. However, such a success cannot be a decisive argument for the truth of so extended theory. One’s clear intuitive apprehension of the ACI’s truth, as witnessed by what Gödel says about his personal experience of its obviousness, also cannot suffice. However, there does exist an intersubjective evidence for ACI, to wit the gigantic range of its successful applications in every domain of human activity — astronomy,
accounting, engineering etc. — the success experienced during the tens of centuries in each civilization.
§2. Now it is in order to pay attention to Turing’s idea of oracle as presented in the mentioned (above) study by Feferman entitled: Turing’s ‘Oracle’: From Absolute to Relative computability and Back. The respective passage (slightly by me abbreviated) runs as follows (emphasis by Feferman).
>>The subject of effective computability began with what were offered as analyses of the absolute limits of effective computability, the immediate primary aim was to establish negative results of the effective unsolvability of various problems in logic and mathematics.
From this the subject turned to refined classifications of unsolvability. […] The germinal step, conceptually, was provided by Turing’s notion of computability relative to an ‘oracle’. At the hands of Post, this provided the beginning of the subject of degrees of unsolvability, less directly provided by Turing’s notion, but mplicit in it, were notions of uniform relative computability.<< Sec. 13.1, Introduction.
Turing did not say much about the way in which an oracle works, but made a very significant statement: that an oracle is no mechanical device, and that a machine equipped with that device can solve problems unsolvable for ordinary machines, lacking such a device. In other words, an oracle is able to find the value of an uncomputable function. More is said on the issue by Turing’s commentators like Andrew Hodges who offers convincing arguments that the decisions of an oracle are, in fact (in Turing’s intention) some acts of mathematical intuition. A similar stance has been taken by Roger Penrose. Thus, the amount of negative results diminishes with successive steps extending the scope of the solvability relative to an oracle. Now, as we know that the inventing of new, more powerful, systems of axioms is due to intellectual intuitions, and that axioms should be credited not only for their intutive obviousness, but much more for an immense number of successful applications, we attain at an answer to Ajdukiewicz-Grzegorczyk problem of the intuitive justification of axioms. This is to the effect that the intuition, being at the bottom of the process in question, proves its mettle by the fact the those axioms in which it has been expressed do successively pass the most severe exam of very differentiated and long-lasting applications.
§3. To conclude this part of discussion, let us observe that the interest in the idea of oracle, as involving the theory of grades of relative computability (solvability), is not confined to circle of speculative philosophers (to which belongs the present author). Presently it is found in the focus of highly technical discussions in mathematical logic. As well as in computer science; in the latter not only at the level of theoretical foundations, but also in the everyday practice. As testified by Feferman in the Conclusion of his penetrative study (Section 13.6.6):
>>The case had been made here that notions of relativized (as compared to absolute) computability theory are essentially involved in actual hardware and software design.<<
I made the above comment on some statements by Feferman, having been encouraged by the fact that his conribution was highly appreciated by Dr. Quinon. I am grateful for her message as when making use of it, I gained a new pespective in my thinking about computability.
In this perspective, I think that her research in the extensional equivalence and intensional differences between various treatments of Turingian model of computation should embrace the issue of the gradation of of relative computability; one may also say “relative solvability” for the former is a special case of the latter: computing is one of the ways of problem-solving.
Turings (1939) model of problem-solving makes more precise the notion of mathematical intuition, and then we can moce precisely put important questions, say: whether such an intuition can be obtained by artificial intelligence?
Now, when considering other theoretical models of computability (as those of Post, Church, Markov, Kleene, etc.), can we find in them an analog to relative computability as defined in terms of oracle? May be, the answer in the affirmative would be trivial, but I ask so being aware of my limited in that area expertise.
Another result which may be expected from Dr. Quinon’s inquiries is related to the question being the title of her abstract: “What “computing” means?” Should the notion of computing embrace the non-algorithmic activity performed by an oracle, namely that of finding the value (does it mean computing?) of an uncomputable function? If there is a puzzle in this question, what should be done to improve the terminology?
There would be more interesting issues inspired by Quinon’s project, but let those listed above suffice for the time being.
Recommended References
Items 1 and refer to the present author’s articles in which the concept of oracle is discussed, fairly extensively, with quoting and commenting Turing’s (1939) texts. Note that in both titles there appears the phrase “ever higher solvability” closely related to the notions of effective computability, effective unsolvability and relativized (as compared to absolute) computability — as employed by Feferman (quotations in §1 and §2 and the title in §1). Items 3 and 4 are concerned with the idea of oracle. Item 5 is related to that idea as dealing with Gödel’s theorem which can be used to exemplify Turing’s relative computability with respect to oracles.
1. “The progress of science from a computational point of view: the drive towards ever higher solvability” in: Foundations of Computing and Decision Sciences, Volume 44, Issue 1, 2019, pp. 11-26.
2. “Does science progress towards ever higher solvability through feedbacks between insights and routines? ” in: Studia Semiotyczne, XXXII no.2 (2018), pp. 153-185.
3. A.M. Turing. “Systems of Logic Based on Ordinals”. 1939. URL – local copy: turing-1939.pdf.
4. Robert I. Soare. Turing Oracle Machines, Online Computing, and Three Displacements in Computability Theory. 2009. URL – local copy: soare.pdf.
5. Samuel R. Buss. On Gödel’s Theorems on Lengths of Proofs I:
Number of Lines and Speedup for Arithmetics. 1992. URL – local copy : god-buss.pdf.
6. Paula Quinon. Abstract of the paper: What computiong” means
The Church-Turing thesis identifies the intuitive concept of what means ˙to compute˙ with a formal model of computation. There are multiple models of computation and all of them can be proved to be extensionally equivalent (they capture the same functions, such as ˙identity˙, or ˙the next element of the sequence˙). However, despite the extensional equivalence, models differ intensionally (they capture different aspects of computation, for instance computations on abstract natural numbers are intensionally different from computations performed by a machine using concrete electric signals). The main objective of this project is to characterize intensional differences between various concepts of computation.
Postscript
When browsing my notes on solvability, I found a very illuminating remark by Gregory Chaitin. His phrase “intuition and creativity” may be interpreted as an exemplification of oracle, while the infinite chain of ever stronger axiomatic systems does resemble Turing’s ordering of logics.
Gödel’s own belief was that in spite of his incompleteness theorem there is in fact no limit to what mathematicians can achieve by using their intuition and creativity instead of depending only on logic and the axiomatic method. He believed that any important mathematical question could eventually be settled, if necessary by adding new fundamental principles to math, that is, new axioms or postulates. Note however that this implies that the concept of mathematical truth becomes something dynamic that evolves, that changes with time, as opposed to the traditional view that mathematical truth is static and eternal. See “Chaitin interview for Simply Gödel website” (9 February 2008).
Consider the phrase I have emphasised (through red type). Does the process of “adding new fundamental principles” belong to the processes of computation? If so, which model of computation would explain the intuitive meaning of the a phrase like that? This is a question which seems to be implied by Quinon’s plan of comparing the existing explications of the term “computing”.
If we could see an artificial neural network solving the problem:
1. supposedly “using statements” that could not be proved by any axioms constituting its operation,
2. in a way in which the manifestation of theses, which mathematicians can not prove, is occuring
– should we assume the functioning of an ‘Oracle’ in it?
Perhaps specialists in artificial neural networks (or other computational techniques like deep learning) could share examples of such machines (for which points 1 and 2 are satisfied) even now.
In this case, the manifestation of the “effect” of the ‘Oracle’ would be a consequence of the construction of the computing system on “meta-level”.
– There is more (productive, significant) information “coded” in hardware, than that which results from axioms directly related to calculations.
Regardless of whether the concept of the ‘Oracle’ is reserved only for a certain quality of human reasoning (intuition), its philosophical source may be similar confusion of the levels of considerations / systems / calculations (lack of language stratification) which causes consequences similar to the ‘ liars’ paradox ‘.
Naively:
Some of the “axioms” that give the effect of the ‘Oracle’ (a clear belief in correctness) are contained in the hardware (brain) “in which” the reasoning conscious mind functions.
These axioms are implicitly included in the functional construction of this “equipment” due to the fact, that their prior inclusion was successful in the description of the environment, enabling survival (not only of evolving human species but also learning and competing mathematicians)
– they reflect the unproven but tested truths about (mathematical) logos of reality (and data sets available directly to the individual on mathematical theories).
Constituting an environment in which the mind deliberately reasoning (proves mathematical claims) such assumptions are in the “meta-system”, making us take for real what we can not prove in the (first) level of (mathematical) language. Systems in the brain (in which “calculations” are made that allow the functioning of a conscious mind) act according to these assumptions even if (consciously) they do not form part of our theory.
Referring to the title of Paula Quinon’s original presentation, “What does computing mean?”, I see two directions of answers to the posed question.
The first direction is to study the classical model of computation (let’s call it ‘the Turing model’) and to explain the differences between various, extensionally equivalent, mathematical descriptions of this model, e.g. a description in terms of Turing machines and a description in terms of recursive functions. This direction therefore consists in explaining the intensional differences between different ways of representing the same model.
In this context he question to Paula Quinon would be this: for what reasons does she find it important to reveal these differences (since despite these differences, the power of the model, i.e. the range of problems it solves, does not change)?
I feel intuitively the point here is the usefulness at the level of explanation: that is, certain descriptions would allow us to understand better what the solution to a given problem is than others. And going to a more general level: some descriptions would also better explain the essence of mechanical problem solving on the basis of algorithms (and it seems for me that the best explanation here is provided by Universal Turing Machine formalism).
The second direction of the answer to the above question (What computing means?) is the study of various non-classical models of computation (hypercomputation) — which, according to their theory, provide solvability of a broader class of problems than the classical Turing model. Therefore, they are not extensionally equivalent to the Turing model. Such models include, for example, the model of analog-continuous computation (in this case we allow processing of continuous signals, described mathematically with real numbers) or various infinitystic models (in this case we allow performing infinite number of operations in a finite time).
In my opinion, procedures compliant with non-Turing models cannot be denied the name of computations, even if (according to the Church-Turing hypothesis) their practical implementation seems problematic. The theory of this kind of computation, being a part of theoretical computer science, seems to me necessary to search in nature for physical systems that would be able to provide (contrary to the Church-Turing hypothesis) the solvability of problems, that are uncomputable under Turing model…
That’ s all for the beginning, :)
As an editor of the blog I encourage everyone to further discussion…
I agree withPaweł Stacewicz’s comment in both points. I see as justified his encouragement that Paula Quinon should explain closer her motivation for analysing intensional differences among the various extesionally equivalent approaches to the notion of computability. I believe that it is a reasonable project in order to better understand – due to a comparative analysis – merits of each solution. But the Author may have had a different intention.
By the way – a historical reamark. Carnap is neither the unique nor the first to promote the method of explication. The very term “explication” is his terminological invention, indeed, but the idea goes back to the beginnings of Analytic Philosophy connected with G.E.Moore, the one who discussed “paradox of analysis”, being a paradox of explication as well. A short report on this subject is found in my entry “Analiza logiczna” in “Mała encyklopedia logiki”, page 19.
I share Stacewicz’s appreciation of hyper-computational models as relevant to the issues of natural computing. Moreover, I kindly request for an interest in computing by oracle machines, as discused in my papers listed in References at the end of my first comment.
Being an outsider to the debates in the philosophy of mathematics while taking a keen interest in AI, cognitive science and the history and philosophy thereof, let me add some general remarks to this debate that may already have been covered in a body of literature of which I have very little knowledge. I see (or rather vaguely sense) two related points in Witold Marciszewski’s treatment of Paula Quinon’s paper: first, what is the nature and role of mathematical intuition? Second, what are the limits of computation?
I. On mathematical intuition: one could give two interpretations of its import on mathematics.
1. The weak, ‘hypothetico-deductive’ version (that might be well compatible with scientific and mathematic orthodoxy): mathematical intuition is analogous to the role of intuition in the empirical sciences as conceived of by Einstein Popper and other non-inductivists, and as such well-circumscribed in its role. It is important to the context of discovery, where hypotheses might be formed rather freely and then put to the test. The testing belongs to the context of justification though, where fundamental principles apply that are not subject to human inventiveness.
2. The strong, ‘constructivist’ version (the view that Chaitin seems to ascribe to Gödel): mathematical principles are human inventions, so there are no limits to what mathematics intuition could achieve except the law of non-contradiction and other elementary logical principles. Perhaps even as far down as number concepts but certainly on the level of higher-order principles, mathematics is a human invention (was the number zero discovered or invented by Indian mathematicians?).
I am not going to adjudicate these positions here (they do not exhaust the space of possible views anyway), but they might have a bearing on the second question.
II. On the limits of computation: I am frequently struck by the somewhat inflationary and fuzzy use of the notion of computation in a range of disciplines that usually strive for conceptual precision. Rocks do not implement computations for sure, and I have some reserve against the notion of physical computation in systems that are not machines designed to compute. So I suggest to start with gently applying Occam’s razor and resort to Turing’s original definition. Although this might not resolve all issues that emerge further down the line, it might help us to some clarity. Let me try:
(i) The domain of computable functions is exhausted by the functions that are ‘effectively calculable’ in such a way that they can be solved, in principle, by a logical computing machine (LCM) as described by Turing.
(ii) A LCM comprises of a finite set of symbols, a finite set of possible states, a transition function and a potentially infinite memory.
Hence, computable is everything that an LCM or ‘Turing Machine’ can solve. This is has often been taken to amount to the claim that computable is everything that any machine can solve – which dies not seem to be true, because machines are conceivable that could solve more than the set of functions computable by LCMs. Now, the question is whether or not we should refer to whatever happens in those more powerful machines as computation, and why. If we take Turing’s definition at face value, computability is always relative to the design of his LCM.
But then, there is Gandy’s “Thesis M” (1980), which states that “whatever can be calculated by a machine can be calculated by a Turing machine” (Copeland 2009, 10) and, conversely, “anything that a machine can do is computable” (Hodges 2008b, 86 f) – which is a very different claim from Turing-computability. But then again, there is Turing’s notion of an ‘oracle’, which could solve all the functions that an LCM cannot solve. There are two divergent interpretations of what the oracle could be and accomplish:
1. If a machine is necessarily restricted to computable operations in terms of Turing’s LCM, there is no way of conceiving and building a machine that could solve any non-computable problem. There will be principled limitations on what a machine, not only a LCM, could possibly accomplish (Hodges’ interpretation).
2. If there could be a machine that solves non-Turing-computable functions, Turing’s oracle could become a real machine in principle. There will be no principled limitations on what a machine could possibly accomplish, but that machine would not be a LCM (Copeland’s interpretation).
So, looping back to the distinction between different readings of mathematical intuition above, the strong constructivist ‘no principled limitations’ reading seems to have a counterpart in the notion of ‘no principled limitations’ on what a machine could accomplish, whereas the weaker reading has a counterpart in the notion of ‘principled limitations’ on what a machine could accomplish. I do not say ‘parallel’ here but ‘counterpart’ because I see two interestingly contrasting implications:
A. If mathematical principles are human inventions, it cannot be ruled out that human beings find Turing-computable solutions to functions to which they currently do not have Turing-computable solutions. There would be no need for an oracle. Strong Artificial Intelligence might be possible, and it might ultimately be Turing-machine-based.
B. If human beings could build a machine that solves non-Turing-computable functions, and if the nature of the human mind involves non-Turing-computable elements, this machine would not be a Turing Machine. We could build an oracle-machine. Strong Artificial Intelligence would be possible but it would not be Turing-machine-based AI.
In this sense, and unless I am guilty of forcing an analogy here, the question of the “meaning of computation” has much to do with any possible limitations on human inventiveness, or the absence thereof, in one way (A.) or another (B.).
I think that Hajo Greif’s attempt to classify various stances in philosophy of mathematics is successful, with the exception of item I.2. The Author attributes to Gödel “the strong, constructivist˙ version (the view that Chaitin seems to ascribe to Gödel): that mathematical principles are human inventions.”
In fact, the contrary is the case. Gödel is famous as one who strongly opposed constructivism, as frequently repeated in his talks with Hao Wang. Even more, Gödel is commonly regarded as the leader of the Platonic camp, connecting Platonism with pragmatism, like Quine, Putnam, Kreisel et al. Their position is in a way similar to that mentioned in item I.1: mathematical objects belong to the objective reality, bur are just hypothetical, and their existence has to be tested by a reduction to less uncertain objects, e.g., natural numbers, being better confirmed than, e.g., inaccessible cardinals.
I fully concur with Witold Marciszewski here. Actually, I did not mean to ascribe a constructivist position to Gödel but reiterated what In believed to be such an ascription in the literature (Chaitin). That owes to my far-reaching ignorance of Gödel’s work. I am hopeful though that this will not affect my systematic point, which is descriptive and should be able to stand without Gödel’s support.
In my previous comment I opposed Hajo Greif’s claim about Gödel’s stance in philosophy of mathematics, but without a hint on references.
There would be a lot of them. I find specially useful WILFRIED SIEG’s paper “On mind & Turing’s machines” in “Natural Computing” (2006) as containing an ample set of references to Gödel’s studies in philosophy of mathematics. Also in the content of the paper (though mainly devoted to Turing), one can find important remarks on Gödel’s position. To inform about the content, I enclose the abstract of Sieg’s contribution.
Abstract.
Turing’s notion of human computability is exactly right not only for obtaining
a negative solution of Hilbert’s Entscheidungsproblem that is conclusive, but also for achieving a precise characterization of formal systems that is needed for the general formulation of the incompleteness theorems. The broad intellectual context reaches back to Leibniz and requires a focus on mechanical procedures; these procedures are to be carried out by human computers without invoking higher cognitive capacities. The question whether there are strictly broader notions of effectiveness has of course been asked for both cognitive and physical processes. I address this question not in any general way, but rather by focusing on aspects of mathematical reasoning that transcend mechanical procedures. Section 1 discusses Go¨ del’s perspective on mechanical computability as articulated in his [193?], where he drew a dramatic conclusion from the undecidability of certain Diophantine propositions, namely, that mathematicians cannot be replaced by machines. That theme is taken up in the Gibbs Lecture of 1951; Gödel argues there in greater detail that the human mind infinitely surpasses the powers of any finite achine. An analysis of the argument is presented in Section 2 under the heading Beyond calculation. Section 3 is entitled Beyond discipline and gives Turing’s view of intelligent machinery; it is devoted to the seemingly sharp conflict between Go¨ del’s and Turing’s views on mind. Their deeper disagreement really concerns the nature of machines, and I’ll end with some brief remarks on (supra-) mechanical devices in Section 4.