You are currently browsing the tag archive for the ‘algorithmically decidable’ tag.
(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)
In this post I address two critical issues, as raised in private correspondence with researchers, which may illuminate some objections to Gödel’s reasoning and conclusions that have been raised elsewhere by Wittgenstein, Floyd, Putnam et al.:
(i) By Rosser’s reasoning, doesn’t simple consistency suffice for defining an undecidable arithmetical proposition?
(ii) Doesn’t Gödel’s undecidable formula assert its own unprovability?
NOTE: The following correspondence refers copiously to this paper that was presented in June 2015 at the workshop on Hilbert’s Epsilon and Tau in Logic, Informatics and Linguistics, University of Montpellier, France.
A: Doesn’t simple consistency suffice for defining Rosser’s undecidable arithmetical proposition?
“You claim that the PA system is -inconsistent, and that Gödel’s first theorem holds vacuously. But by Rosser’s result, simple consistency suffices.“
Well, it does seem surprising that Rosser’s claim—that his ‘undecidable’ proposition only assumes simple consistency—has not been addressed more extensively in the literature. Number-theoretic expositions of Rosser’s proof have generally remained either implicit or sketchy (see, for instance, this post).
Note that Rosser’s proposition and reasoning involve interpretation of an existential quantifier, whilst Gödel’s proposition and reasoning only involve interpretation of a universal quantifier.
The reason why Rosser’s claim is untenable is that—in order to interpret the existential quantifier as per Hilbert’s -calculus—Rosser’s argument needs to assume his Rule C (see Elliott Mendelson, Introduction to Mathematical Logic, 1964 ed., p.73), which implicitly implies that Gödel’s arithmetic P—in which Rosser’s argumentation is grounded—is -consistent .
See, for instance, this analysis of (a) Wang’s outline of Rosser’s argument on p.5, (b) Beth’s outline of Rosser’s argument on p.6, and (c) Mendelson’s exposition of Rosser’s argument in Section 4.2 on p.8.
Moreover, the assumption is foundationally fragile, because Rule C invalidly assumes that we can introduce an ‘unspecified’ formula denoting an ‘unspecified’ numeral into PA even if the formula has not been demonstrated to be algorithmically definable in terms of the alphabet of PA.
See Theorem 8.5 and following remarks in Section 8, pp.7-8 of this paper that was presented in June 2015 at the workshop on Hilbert’s Epsilon and Tau in Logic, Informatics and Linguistics, University of Montpellier, France.
B: As I see it, rule C is only a shortcut.
“As I see it, rule C is only a shortcut; it is totally eliminable. Moreover, it is part of predicate logic, not of the Peano’s arithmetic.“
Assuming that Rule C is a short cut which can always be eliminated is illusory, and is tantamount to invalidly (see Corollary 8.6, p.17 of the Epsilon 2015 paper) claiming that Hilbert’s calculus is a conservative extension of the first-order predicate calculus.
Reason: Application of Rule C invalidly (see Theorem 8.5 and following remarks in Section 8, pp.7-8 of the Epsilon 2015 paper) involves introduction of a new individual constant, say , in a first-order theory (see Mendelson 1964, p.74, I(iv)); ‘invalidly’ since Rule C does not qualify that must be algorithmically computable from the alphabet of —which is necessary if is first-order.
Notation: We use square brackets to indicate that the expression within the brackets denotes a well-formed formula of a formal system, say , that is to be viewed syntactically merely as a first-order string of —i.e, one which is finitarily constructed from the alphabet of the language of —without any reference to its meaning under any interpretation of .
Essentially, Rule C mirrors in the intuitionistically objectionable postulation that the formula of can always be interpreted as:
holds for some element
in the domain of the interpretation of under which the formula interprets as the relation .
The Epsilon 2015 paper shows that this is not a valid interpretation of the formula under any finitary, evidence-based, interpretation of .
That, incidentally, is a consequence of the proof that PA is not -consistent; which itself is a consequence of (Theorem 7.1, p.15, of the Epsilon 2015 paper):
Provability Theorem for PA: A PA formula is provable if, and only if, interprets as an arithmetical relation that is algorithmically computable as always true (see Definition 3, p.7, of the Epsilon 2015 paper) over the structure of the natural numbers.
Compare with what Gödel has essentially shown in his famous 1931 paper on formally undecidable arithmetical propositions, which is that (Lemma 8.1, p.16, of the Epsilon 2015 paper):
Gödel: There is a PA formula —which Gödel refers to by its Gödel number —which is not provable in PA, even though interprets as an arithmetical relation that is algorithmically verifiable as always true (see Definition 4, p.7, of the Epsilon 2015 paper) over the structure of the natural numbers.
C: If you by-pass the intuitionist objections, would all logicist and post-formalist theories hold?
“If I have understood correctly, you claim that the PA system is -inconsistent from an intuitionistic point of view? If you by-pass the intuitionist objections, would all logicist and post-formalist theories hold?“
There is nothing to bypass—the first-order Peano Arithmetic PA is a formal axiomatic system which is -inconsistent as much for an intuitionist, as it is for a realist, a finitist, a formalist, a logicist or a nominalist.
Philosophers may differ about beliefs that are essentially unverifiable; but the -incompleteness of PA is a verifiable logical meta-theorem that none of them would dispute.
D: Isn’t Gödel’s undecidable formula —which Gödel refers to by its Gödel number —self-referential?
Isn’t Gödel’s undecidable formula —which Gödel refers to by its Gödel number —self-referential and covertly paradoxical?
According to Wittgenstein it interprets in any model as a sentence that is devoid of sense, or even meaning. I think a good reason for this is that the formula is simply syntactically wrongly formed: the provability of provability is not defined and can not be consistently defined.
What you propose may be correct, but for automation systems of deduction wouldn’t -inconsistency be much more problematic than undecidability?
How would you feel if a syntax rule is proposed, that formulas containing numerals are instantiations of open formulas that may not be part of the canonical language? Too daring, may be?
Let me briefly respond to the interesting points that you have raised.
1. The -inconsistency of PA is a meta-theorem; it is a Corollary of the Provability Theorem of PA (Theorem 7.1, p.15, of the Epsilon 2015 paper).
2. Gödel’s PA-formula is not an undecidable formula of PA. It is merely unprovable in PA.
3. Moreover, Gödel’s PA-formula is provable in PA, which is why the PA formula is not an undecidable formula of PA.
4. Gödel’s PA-formula is not self-referential.
5. Wittgenstein correctly believed—albeit purely on the basis of philosophical considerations unrelated to whether or not Gödel’s formal reasoning was correct—that Gödel was wrong in stating that the PA formula asserts its own unprovability in PA.
Reason: We have for Gödel’s primitive recursive relation that:
is true if, and only if, the PA formula is provable in PA.
However, in order to conclude that the PA formula asserts its own unprovability in PA, Gödel’s argument must further imply—which it does not—that:
is true (and so, by Gödel’s definition of , the PA formula is not provable in PA) if, and only if, the PA formula is provable in PA.
In other words, for the PA formula to assert its own unprovability in PA, Gödel must show—which his own argument shows is impossible, since the PA formula is not provable in PA—that:
The primitive recursive relation is algorithmically computable as always true if, and only if, the arithmetical relation is algorithmically computable as always true (where is the arithmetical interpretation of the PA formula over the structure of the natural numbers).
6. Hence, Gödel’s PA-formula is not covertly paradoxical.
7. IF Wittgenstein believed that the PA formula is empty of meaning and has no valid interpretation, then he was wrong, and—as Gödel justifiably believed—he could not have properly grasped Gödel’s formal reasoning that:
(i) ‘ is not -provable’ is a valid meta-theorem if PA is consistent, which means that:
‘If PA is consistent and we assume that the PA formula is provable in PA, then the PA formula must also be provable in PA; from which we may conclude that the PA formula is not provable in PA’
(ii) ‘ is not -provable’ is a valid meta-theorem ONLY if PA is -consistent, which means that:
‘If PA is -consistent and we assume that the PA formula is provable in PA, then the PA formula must also be provable in PA; from which we may conclude that the PA formula is not provable in PA’.
8. In fact the PA formula has the following TWO meaningful interpretations (the first of which is a true arithmetical meta-statement—since the PA formula is provable in PA for any PA-numeral —but the second is not—since the PA formula is not provable in PA):
(i) For any given natural number , there is an algorithm which will verify that each of the arithmetical meta-statements ‘ is true’, ‘ is true’, …, ‘ is true’ holds under the standard, algorithmically verifiable, interpretation of PA (see \S 5, p.11 of the Epsilon 2015 paper);
(ii) There is an algorithm which will verify that, for any given natural number , the arithmetical statement ‘ is true’ holds under the finitary, algorithmically computable, interpretation of PA (see \S 6, p.13 of the Epsilon 2015 paper).
9. IF Wittgenstein believed that the PA formula is not a well-defined PA formula, then he was wrong.
Gödel’s definition of the PA formula yields a well-formed formula in PA, and cannot be treated as ‘syntactically wrongly formed’.
10. The Provability Theorem for PA shows that both ‘proving something in PA’ and ‘proving that something is provable in PA’ are finitarily well-defined meta-mathematical concepts.
11. The Provability Theorem for PA implies that PA is complete with respect to the concepts of satisfaction, truth and provability definable in automated deduction systems, which can only define algorithmically computable truth.
12. The Provability Theorem for PA implies that PA is categorical, so you can introduce your proposed syntax rule ONLY if it leads to a conservative extension of PA.
13. Whether ‘daring’ or not, why would you want to introduce such a rule?
E: Consider these two statements of yours …
Consider these two statements of yours:
“(iv): is the Gödel-number of the formula of PA” and
“D(4): Gödel’s PA-formula is not self-referential.”
If ‘‘ is the Gödel-number of the open formula in para (iv), and the second argument of the closed formula in para D(4) is ‘‘, then the second formula is obtained by instantiating the variable ‘‘ in the first with its own Gödel-number.
So how would you call, in one word, the relation between the entire formula (in D(4)) and its second argument?
Para D(4) is an attempt to clarify precisely this point.
1. Apropos the first statement ‘(iv)’ cited by you:
From a pedantic perspective, the “relation between the entire formula (in D(4)) and its second argument” cannot be termed self-referential because the “second argument”, i.e., , is the Gödel-number of the PA formula , and not that of “the entire formula (in 4)”, i.e., of the formula itself (whose Gödel number is ).
Putting it crudely, is neither self-referential—nor circularly defined—because it is not defined in terms of , but in terms of .
2. Apropos the second statement ‘D(4)’ cited by you:
I would interpret:
Gödel’s PA-formula is self-referential
to mean, in this particular context, that—as Gödel wrongly claimed:
asserts its own unprovability in PA.
Now, if we were to accept the claim that is self-referential in the above sense, then (as various critics of Gödel’s reasoning have pointed out) we would have to conclude further that Gödel’s argument leads to the contradiction:
is true—and so, by Gödel’s definition of —the PA formula is not provable in PA—if, and only if, the PA formula is provable in PA.
However, in view of the Provability Theorem of PA (Theorem 7.1, p.15, of the Epsilon 2015 paper), this contradiction would only follow if Gödel’s argument were to establish (which it does not) that:
The primitive recursive relation is algorithmically computable as always true if, and only if, the arithmetical interpretation of the PA formula is algorithmically computable as always true over the structure of the natural numbers.
The reason Gödel cannot claim to have established the above is that his argument only proves the much weaker meta-statement:
The arithmetical interpretation of the PA formula is algorithmically verifiable as always true over the structure of the natural numbers.
Ergo—contrary to Gödel’s claim— Gödel’s PA-formula is not self-referential (and so, even though Gödel’s claimed interpretation of what his own reasoning proves is wrong, there is no paradox in Gödel’s reasoning per se)!
F: Is the PA system -inconsistent without remedy?
Is the PA system -inconsistent without remedy? Is it possible to introduce a new axiom or new rule which by-passes the problematic unprovable statements of the Gödel-Rosser Theorems?
1. Please note that the first-order Peano Arithmetic PA is:
(i) consistent (Theorem 7.3, p.15, of the Epsilon 2015 paper); which means that for any PA-formula , we cannot have that both and are Theorems of PA;
(ii) complete (Theorem 7.1, p.15, of the Epsilon 2015 paper); which means that we cannot add an axiom to PA which is not a Theorem of PA without inviting inconsistency;
(iii) categorical (Theorem 7.2, p.15, of the Epsilon 2015 paper); which means that if is an interpretation of PA over a structure , and is an interpretation of PA over a structure , then and are identical and denote the structure of the natural numbers defined by Dedekind’s axioms; and so PA has no model which contains an element that is not a natural number (see Footnote 54, p.16, of the Epsilon 2015 paper).
2. What this means with respect to Gödel’s reasoning is that:
(i) PA has no undecidable propositions, which is why it is not -consistent (Corollary 8.4, p.16, of the Epsilon 2015 paper);
(ii) The Gödel formula is not provable in PA; but it is algorithmically verifiable as true (Corollary 8.3, p.16, of the Epsilon 2015 paper) under the algorithmically verifiable standard interpretation of PA (see Section 5, p.11, of the Epsilon 2015 paper) over the structure of the natural numbers;
(iii) The Gödel formula is not provable in PA; and it is algorithmically computable as false (Corollary 8.3, p.16, of the Epsilon 2015 paper) under the algorithmically computable finitary interpretation of PA (see Section 6, p.13, of the Epsilon 2015 paper) over the structure of the natural numbers;
(iv) The Gödel formula is provable in PA; and it is therefore also algorithmically verifiable as true under the algorithmically verifiable standard interpretation of PA over the structure of the natural numbers—which means that the logic by which the standard interpretation of PA assigns values of ‘satisfaction’ and ‘truth’ to the formulas of PA (under Tarski’s definitions) may be paraconsistent (see http://plato.stanford.edu/entries/logic-paraconsistent) since PA is consistent;
(v) The Gödel formula is provable in PA; and it is therefore algorithmically computable as true (Corollary 8.2, p.16, of the Epsilon 2015 paper) under the algorithmically computable finitary interpretation of PA over the structure of the natural numbers.
3. It also means that:
(a) The “Gödel-Rosser Theorem” is not a Theorem of PA;
(b) The “unprovable Gödel sentence” is not a “problematic statement”;
(c) The “PA system” does not require a “remedy” just because it is “-inconsistent”;
(d) No “new axiom or new rule” can “by-pass the unprovable sentence”.
4. Which raises the question:
Why do you see the “unprovable Gödel sentence” as a “problematic statement” that requires a “remedy” which must “by-pass the unprovable sentence”?
(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)
Ferguson’s and Priest’s thesis
In a brief, but provocative, review of what they term as “the enduring evolution of logic” over the ages, the authors of Oxford University Press’ recently released ‘A Dictionary of Logic‘, philosophers Thomas Macaulay Ferguson and Graham Priest, take to task what they view as a Kant-influenced manner in which logic is taught as a first course in most places in the world:
“… as usually ahistorical and somewhat dogmatic. This is what logic is; just learn the rules. It is as if Frege had brought down the tablets from Mount Sinai: the result is God-given, fixed, and unquestionable.”
Ferguson and Priest conclude their review by remarking that:
“Logic provides a theory, or set of theories, about what follows from what, and why. And like any theoretical inquiry, it has evolved, and will continue to do so. It will surely produce theories of greater depth, scope, subtlety, refinement—and maybe even truth.”
However, it is not obvious whether that is prescient optimism, or a tongue-in-cheek exit line!
A nineteenth century parody of the struggle to define ‘truth’ objectively
For, if anything, the developments in logic since around 1931 has—seemingly in gross violation of the hallowed principle of Ockham’s razor, and its crude, but highly effective, modern avatar KISS—indeed produced a plethora of theories of great depth, scope, subtlety, and refinement.
These, however, seem to have more in common with the, cynical, twentieth century emphasis on subjective, unverifiable, ‘truth’, rather than with the concept of an objective, evidence-based, ‘truth’ that centuries of philosophers and mathematicians strenuously struggled to differentiate and express.
A struggle reflected so eloquently in this nineteenth century quote:
“When I use a word,” Humpty Dumpty said, in rather a scornful tone, “it means just what I choose it to mean—neither more nor less.”
“The question is,” said Alice, “whether you can make words mean so many different things.”
“The question is,” said Humpty Dumpty, “which is to be master—that’s all.”
… Lewis Carroll (Charles L. Dodgson), ‘Through the Looking-Glass’, chapter 6, p. 205 (1934 ed.). First published in 1872.
Making sense of mathematical propositions about infinite processes
It was, indeed, an epic struggle which culminated in the nineteenth century standards of rigour successfully imposed—in no small measure by the works of Augustin-Louis Cauchy and Karl Weierstrasse—on verifiable interpretations of mathematical propositions about infinite processes involving real numbers.
A struggle, moreover, which should have culminated equally successfully in similar twentieth century standards—on verifiable interpretations of mathematical propositions containing references to infinite computations involving integers—sought to be imposed in 1936 by Alan Turing upon philosophical and mathematical discourse.
The Liar paradox
For it follows from Turing’s 1936 reasoning that where quantification is not, or cannot be, explicitly defined in formal logical terms—eg. the classical expression of the Liar paradox as ‘This sentence is a lie’—a paradox cannot per se be considered as posing serious linguistic or philosophical concerns (see, for instance, the series of four posts beginning here).
Of course—as reflected implicitly in Kurt Gödel’s seminal 1931 paper on undecidable arithmetical propositions—it would be a matter of serious concern if the word ‘This’ in the English language sentence, ‘This sentence is a lie’, could be validly viewed as implicitly implying that:
(i) there is a constructive infinite enumeration of English language sentences;
(ii) to each of which a truth-value can be constructively assigned by the rules of a two-valued logic; and,
(iii) in which ‘This’ refers uniquely to a particular sentence in the enumeration.
Gödel’s influence on Turing’s reasoning
However, Turing’s constructive perspective had the misfortune of being subverted by a knee-jerk, anti-establishment, culture that was—and apparently remains to this day—overwhelmed by Gödel’s powerful Platonic—and essentially unverifiable—mathematical and philosophical 1931 interpretation of his own construction of an arithmetical proposition that is formally unprovable, but undeniably true under any definition of ‘truth’ in any interpretation of arithmetic over the natural numbers.
Otherwise, I believe that Turing could easily have provided the necessary constructive interpretations of arithmetical truth—sought by David Hilbert for establishing the consistency of number theory finitarily—which is addressed by the following paper due to appear in the December 2016 issue of ‘Cognitive Systems Research‘:
What is logic: using Ockham’s razor
Moreover, the paper endorses the implicit orthodoxy of an Ockham’s razor influenced perspective—which Ferguson and Priest seemingly find wanting—that logic is simply a deterministic set of rules that must constructively assign the truth values of ‘truth/falsity’ to the sentences of a language.
It is a view that I expressed earlier as the key to a possible resolution of the EPR paradox in the following paper that I presented on 26’th June at the workshop on Emergent Computational Logics at UNILOG’2015, Istanbul, Turkey:
where I introduced the definition:
A finite set of rules is a Logic of a formal mathematical language if, and only if, constructively assigns unique truth-values:
(a) Of provability/unprovability to the formulas of ; and
(b) Of truth/falsity to the sentences of the Theory which is defined semantically by the -interpretation of over a structure .
I showed there that such a definitional rule-based approach to ‘logic’ and ‘truth’ allows us to:
Equate the provable formulas of the first order Peano Arithmetic PA with the PA formulas that can be evidenced as `true’ under an algorithmically computable interpretation of PA over the structure of the natural numbers;
Adequately represent some of the philosophically troubling abstractions of the physical sciences mathematically;
Interpret such representations unambiguously; and
First that the concept of infinity is an emergent feature of any mechanical intelligence whose true arithmetical propositions are provable in the first-order Peano Arithmetic; and
Second that discovery and formulation of the laws of quantum physics lies within the algorithmically computable logic and reasoning of a mechanical intelligence whose logic is circumscribed by the first-order Peano Arithmetic.
(Notations, non-standard concepts, and definitions used commonly in these investigations are detailed in this post.)
A Economist: The return of the machinery question
In a Special Report on Artificial Intelligence in its issue of 25th June 2016, ‘The return of the machinery question‘, the Economist suggests that both cosmologist Stephen Hawking and enterpreneur Elon Musk share to some degree the:
“… fear that AI poses an existential threat to humanity, because superintelligent computers might not share mankind’s goals and could turn on their creators”.
B Our irrational propensity to fear that which we are drawn to embrace
Surprising, since I suspect both would readily agree that, if anything should scare us, it is our irrational propensity to fear that which we are drawn to embrace!
And therein should lie not only our comfort, but perhaps also our salvation.
For Artificial Intelligence is constrained by rationality; Human Intelligence is not.
An Artificial Intelligence must, whether individually or collectively, create and/or destroy only rationally. Humankind can and does, both individually and collectively, create and destroy irrationally.
C Justifying irrationality
For instance, as the legatees of logicians Kurt Goedel and Alfred Tarski have amply demonstrated, a Human Intelligence can easily be led to believe that some statements of even the simplest of mathematical languages—Arithmetic—must be both ‘formally undecidable’ and ‘true’, even in the absence of any objective yardstick for determining what is ‘true’!
D Differentiating between Human reasoning and Mechanistic reasoning
An Artificial Intelligence, however, can only treat as true that which can be proven—by its rules—to be true by an objective assignment of ‘truth’ and ‘provability’ values to the propositions of the language that formally expresses its mechanical operations—Arithmetic.
The implications of the difference are not obvious; but that the difference could be significant is the thesis of this paper which is due to appear in the December 2016 issue of Cognitive Systems Research:
E Respect for evidence-based ‘truth’ could be Darwinian
More importantly, the paper demonstrates that both Human Intelligence—whose evolution is accepted as Darwinian—and Artificial Intelligence—whose evolution it is ‘feared’ may be Darwinian—share a common (Darwinian?) respect for an accountable concept of ‘truth’.
“… importance of the rapport between an organism and its environment”
—an environment that can obviously accommodate the birth, and nurture the evolution, of both intelligences.
So, it may not be too far-fetched to conjecture that the evolution of both intelligences must also, then, share a Darwinian respect for the kind of human values—towards protecting intelligent life forms—that, no matter in how limited or flawed a guise, is visibly emerging as an inherent characteristic of a human evolution which, no matter what the cost could, albeit optimistically, be viewed as struggling to incrementally strengthen, and simultaneously integrate, individualism (fundamental particles) into nationalism (atoms) into multi-nationalism (molecules) and, possibly, into universalism (elements).
F The larger question: Should we fear an extra-terrestrial Intelligence?
From a broader perspective yet, our apprehensions about the evolution of a rampant Artificial Intelligence created by a Frankensteinian Human Intelligence should, perhaps, more rightly be addressed—as some have urged—within the larger uncertainty posed by SETI:
I would argue that any answer would depend on how we articulate the question and that, in order to engage in a constructive and productive debate, we need to question—and reduce to a minimum—some of our most cherished mathematical and scientific beliefs and fears which cannot be communicated objectively.
Christopher Mole is an associate professor of philosophy at the University of British Columbia, Vancouver. He is the author of Attention is Cognitive Unison: An Essay in Philosophical Psychology (OUP, 2011), and The Unexplained Intellect: Complexity, Time, and the Metaphysics of Embodied Thought (Routledge, 2016).
In his preface to The Unexplained Intellect, Mole emphasises that his book is an attempt to provide arguments for (amongst others) the three theses that:
(i) “Intelligence might become explicable if we treat intelligence thought as if it were some sort of computation”;
(ii) “The importance of the rapport between an organism and its environment must be understood from a broadly computational perspective”;
(iii) “ our difficulties in accounting for our psychological orientation with respect to time are indications of the need to shift our philosophical focus away from mental states—which are altogether too static—and towards a theory of the mind in which it is dynamic mental entities that are taken to be metaphysically foundational”.
Mole explains at length his main claims in The Unexplained Intellect—and the cause that those claims serve—in a lucid and penetrating, VI-part, series of invited posts in The Brains blog (a leading forum for work in the philosophy and science of mind that was founded in 2005 by Gualtiero Piccinini, and has been administered by John Schwenkler since late 2011).
In these posts, Mole seeks to make the following points.
We do not currently have a satisfactory account of how minds could be had by material creatures. If such an account is to be given then every mental phenomenon will need to find a place within it. Many will be accounted for by relating them to other things that are mental, but there must come a point at which we break out of the mental domain, and account for some things that are mental by reference to some that are not. It is unclear where this break out point will be. In that sense it is unclear which mental entities are, metaphysically speaking, the most fundamental.
At some point in the twentieth century, philosophers fell into the habit of writing as if the most fundamental things in the mental domain are mental states (where these are thought of as states having objective features of the world as their truth-evaluable contents). This led to a picture in which the mind was regarded as something like a hoard of sentences. The philosophers and cognitive scientists who have operated with this picture have taken their job to be telling us what sort of content these mental sentences have, how that content is structured, how the sentences come to have it, how they get put into and taken out of storage, how they interact with one another, how they influence behaviour, and so on.
This emphasis on states has caused us to underestimate the importance of non-static mental entities, such as inferences, actions, and encounters with the world. If we take these dynamic entities to be among the most fundamental of the items in the mental domain, then — I argue — we can avoid a number of philosophical problems. Most importantly, we can avoid a picture in which intelligent thought would be beyond the capacities of any physically implementable system.
A lot of philosophers think that consciousness is what makes the mind/body problem interesting, perhaps because they think that consciousness is the only part of that problem that remains wholly philosophical. Other aspects of the mind are taken to be explicable by scientific means, even if explanatorily adequate theories of them remain to be specified.
I’ll remind the reader of computability theory’s power, with a view to indicating how it is that the discoveries of theoretical computer scientists place constraints on our understanding of what intelligence is, and of how it is possible.
If we found that we had been conceiving of intelligence in such a way that intelligence could not be modelled by a Turing Machine, our response should not be to conclude that some alternative must be found to a ‘Classically Computational Theory of the Mind’. To think only that would be to underestimate the scope of the theory of computability. We should instead conclude that, on the conception in question, intelligence would (be) absolutely inexplicable. This need to avoid making intelligence inexplicable places constraints on our conception of what intelligence is.
The lesson to be drawn is that, if we think of intelligence as involving the maintenance of satisfiable beliefs, and if we think of our beliefs as corresponding to a set of representational states, then our intelligence would depend on a run of good luck the chances of which are unknown.
My suggestion is that we can reach a more explanatorily satisfactory conception of intelligence if we adopt a dynamic picture of the mind’s metaphysical foundations.
I suggest that something roughly similar is true of us. We are not guaranteed to have satisfiable beliefs, and sometimes we are rather bad at avoiding unsatisfiability, but such intelligence as we have is to be explained by reference to the rapport between our minds and the world.
Rather than starting from a set of belief states, and then supposing that there is some internal process operating on these states that enables us to update our beliefs rationally, we should start out by accounting for the dynamic processes through which the world is epistemically encountered. Much as the three-colourable map generator reliably produces three-colourable maps because it is essential to his map-making procedure that borders appear only where they will allow for three colorability, so it is essential to what it is for a state to be a belief that beliefs will appear only if there is some rapport between the believer and the world. And this rapport — rather than any internal processing considered in isolation from it — can explain the tendency for our beliefs to respect the demands of intelligence.
memory is essentially a form of epistemic retentiveness: One’s present knowledge counts as an instance of memory when and only when it was attained on the basis of an epistemic encounter that lies in one’s past. One can epistemically encounter a proposition as the conclusion of an argument, and so can encounter it before the occurrence of any event to which it pertains, but one cannot encounter an event in that way. In the resulting explanation of memory’s temporal asymmetry, it is the dynamic events of epistemic encountering to which we must make reference. These encounters, and not the knowledge states to which they lead, do the lion’s share of the explanatory work.
A: Simplifying Mole’s perspective
It may help simplify Mole’s thought-provoking perspective if we make an arbitrary distinction between:
(i) The mind of an applied scientist, whose primary concern is our sensory observations of a ‘common’ external world;
(ii) The mind of a philosopher, whose primary concern is abstracting a coherent perspective of the external world from our sensory observations; and
(iii) The mind of a mathematician, whose primary concern is adequately expressing such abstractions in a formal language of unambiguous communication.
My understanding of Mole’s thesis, then, is that:
(a) although a mathematician’s mind may be capable of defining the ‘truth’ value of some logical and mathematical propositions without reference to the external world,
(b) the ‘truth’ value of any logical or mathematical proposition that purports to represent any aspect of the real world must be capable of being evidenced objectively to the mind of an applied scientist; and that,
(c) of the latter ‘truths’, what should interest the mind of a philosopher is whether there are some that are ‘knowable’ completely independently of the passage of time, and some that are ‘knowable’ only partially, or incrementally, with the passage of time.
B. Support for Mole’s thesis
It also seems to me that Mole’s thesis implicitly subsumes, or at the very least echoes, the belief expressed by Chetan R. Murthy (‘An Evaluation Semantics for Classical Proofs‘, Proceedings of Sixth IEEE Symposium on Logic in Computer Science, pp. 96-109, 1991; also Cornell TR 91-1213):
“It is by now folklore … that one can view the values of a simple functional language as specifying evidence for propositions in a constructive logic …”
If so, the thesis seems significantly supported by the following paper that is due to appear in the December 2016 issue of ‘Cognitive Systems Research’:
The CSR paper implicitly suggests that there are, indeed, (only?) two ways of assigning ‘true’ or ‘false’ values to any mathematical description of real-world events.
C. Algorithmic computability
First, a number theoretical relation is algorithmically computable if, and only if, there is an algorithm that can provide objective evidence (cf. ibid Murthy 91) for deciding the truth/falsity of each proposition in the denumerable sequence .
(We note that the concept of `algorithmic computability’ is essentially an expression of the more rigorously defined concept of `realizability’ on p.503 of Stephen Cole Kleene’s ‘Introduction to Metamathematics‘, North Holland Publishing Company, Amsterdam.)
D. Algorithmic verifiability
Second, a number-theoretical relation is algorithmically verifiable if, and only if, for any given natural number , there is an algorithm which can provide objective evidence for deciding the truth/falsity of each proposition in the finite sequence .
We note that algorithmic computability implies the existence of an algorithm that can finitarily decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions, whereas algorithmic verifiability does not imply the existence of an algorithm that can finitarily decide the truth/falsity of each proposition in a well-defined denumerable sequence of propositions.
The following theorem (Theorem 2.1, p.37 of the CSR paper) shows that although every algorithmically computable relation is algorithmically verifiable, the converse is not true:
Theorem: There are number theoretic functions that are algorithmically verifiable but not algorithmically computable.
E. The significance of algorithmic ‘truth’ assignments for Mole’s theses
The significance of such algorithmic ‘truth’ assignments for Mole’s theses is that:
Algorithmic computability—reflecting the ambit of classical Newtonian mechanics—characterises natural phenomena that are determinate and predictable.
Such phenomena are describable by mathematical propositions that can be termed as ‘knowable completely’, since at any point of time they are algorithmically computable as ‘true’ or ‘false’.
Hence both their past and future behaviour is completely computable, and their ‘truth’ values are therefore ‘knowable’ independent of the passage of time.
Algorithmic verifiability—reflecting the ambit of Quantum mechanics—characterises natural phenomena that are determinate but unpredictable.
Such phenomena are describable by mathematical propositions that can only be termed as ‘knowable incompletely’, since at any point of time they are only algorithmically verifiable, but not algorithmically computable, as ‘true’ or ‘false’
Hence, although their past behaviour is completely computable, their future behaviour is not completely predictable, and their ‘truth’ values are not independent of the passage of time.
F. Where Mole’s implicit faith in the adequacy of set theoretical representations of natural phenomena may be misplaced
It also seems to me that, although Mole’s analysis justifiably holds that the:
“ importance of the rapport between an organism and its environment”
has been underacknowledged, or even overlooked, by existing theories of the mind and intelligence, it does not seem to mistrust, and therefore ascribe such underacknowledgement to any lacuna in, the mathematical and epistemic foundations of the formal language in which almost all descriptions of real-world events are currently sought to be expressed, which is the language of the set theory ZF.
G. Any claim to a physically manifestable ‘truth’ must be objectively accountable
Now, so far as applied science is concerned, history teaches us that the ‘truth’ of any mathematical proposition that purports to represent any aspect of the external world must be capable of being evidenced objectively; and that such ‘truths’ must not be only of a subjective and/or revelationary nature which may require truth-certification by evolutionarily selected prophets.
(Not necessarily religious—see, for instance, Melvyn B. Nathanson’s remarks, “Desperately Seeking Mathematical Truth“, in the Opinion piece in the August 2008 Notices of the American Mathematical Society, Vol. 55, Issue 7.)
The broader significance of seeking objective accountability is that it admits the following (admittedly iconoclastic) distinction between the two fundamental mathematical languages:
1. The first-order Peano Arithmetic PA as the language of science; and
2. The first-order Set Theory ZF as the language of science fiction.
“Finitistic reasoning (my read: ‘First-order Peano Arithmetic PA’) is unique because of its clear real-world meaning and its indispensability for all scientific thought. Nonfinitistic reasoning (my read: ‘First-order Set Theory ZF’) can be accused of referring not to anything in reality but only to arbitrary mental constructions. Hence nonfinitistic mathematics can be accused of being not science but merely a mental game played for the amusement of mathematicians.”
The distinction is supported by the formal argument (detailed in the above-cited CSR paper) that:
(i) PA has two, hitherto unsuspected, evidence-based interpretations, the first of which can be treated as circumscribing the ambit of human reasoning about ‘true’ arithmetical propositions; and the second can be treated as circumscribing the ambit of mechanistic reasoning about ‘true’ arithmetical propositions.
What this means is that the language of arithmetic—formally expressed as PA—can provide all the foundational needs for all practical applications of mathematics in the physical sciences. This was was the point that I sought to make—in a limited way, with respect to quantum phenomena—in the following paper presented at Unilog 2015, Istanbul last year:
(Presented on 26’th June at the workshop on ‘Emergent Computational Logics’ at UNILOG’2015, 5th World Congress and School on Universal Logic, 20th June 2015 – 30th June 2015, Istanbul, Turkey.)
(ii) Since ZF axiomatically postulates the existence of an infinite set that cannot be evidenced (and which cannot be introduced as a constant into PA, or as an element into the domain of any interpretation of PA, without inviting inconsistency—see Theorem 1 in 4 of this post), it can have no evidence-based interpretation that could be treated as circumscribing the ambit of either human reasoning about ‘true’ set-theoretical propositions, or that of mechanistic reasoning about ‘true’ set-theoretical propositions.
The language of set theory—formally expressed as ZF—thus provides the foundation for abstract structures that—although of possible interest to philosophers of science—are only mentally conceivable by mathematicians subjectively, and have no verifiable physical counterparts, or immediately practical applications of mathematics, that can materially impact on the study of physical phenomena.
The significance of this distinction can be expressed more vividly in Russell’s phraseology as:
(iii) In the first-order Peano Arithmetic PA we always know what we are talking about, even though we may not always know whether it is true or not;
(iv) In the first-order Set Theory we never know what we are talking about, so the question of whether or not it is true is only of fictional interest.
H. The importance of Mole’s ‘rapport’
Accordingly, I see it as axiomatic that the relationship between an evidence-based mathematical language and the physical phenomena that it purports to describe, must be in what Mole terms as ‘rapport’, if we view mathematics as a set of linguistic tools that have evolved:
(a) to adequately abstract and precisely express through human reasoning our observations of physical phenomena in the world in which we live and work; and
(b) unambiguously communicate such abstractions and their expression to others through objectively evidenced reasoning in order to function to the maximum of our co-operative potential in acieving a better understanding of physical phenomena.
This is the perspective that I sought to make in the following paper presented at Epsilon 2015, Montpellier, last June, where I argue against the introduction of ‘unspecifiable’ elements (such as completed infinities) into either a formal language or any of its evidence-based interpretations (in support of the argument that since a completed infinity cannot be evidence-based, it must therefore be dispensible in any purported description of reality):
(Presented on 10th June at the Epsilon 2015 workshop on ‘Hilbert’s Epsilon and Tau in Logic, Informatics and Linguistics’, 10th June 2015 – 12th June 2015, University of Montpellier, France.)
I. Why mathematical reasoning must reflect an ‘agnostic’ perspective
Moreover, from a non-mathematician’s perspective, a Propertarian like Curt Doolittle would seem justified in his critique (comment of June 2, 2016 in this Quanta review) of the seemingly ‘mystical’ and ‘irrelevant’ direction in which conventional interpretations of Hilbert’s ‘theistic’ and Brouwer’s ‘atheistic’ reasoning appear to have pointed mainstream mathematics for, as I argue informally in an earlier post, the ‘truths’ of any mathematical reasoning must reflect an ‘agnostic’ perspective.
It is a misconception that an arithmetical statement—such as the one constructed by Kurt Gödel (1931. On formally undecidable propositions of Principia Mathematica and related systems I. In M. Davis. 1965. The Undecidable. p25)—can be intuitively true, and yet not follow formally from the axioms and rules of inference of a first-order Peano Arithmetic, .
The misconception arises because actually admits two logical entailments, only one of which—Gödelian provability—has, so far, been formally acknowledged.
However, the other—familiar only in its avatar as the intuitive truth of a proposition under ‘s standard interpretation—does, also, follow formally from the axioms and rules of inference of .
Even when this issue is sought to be addressed, the argument is indirect, and this point remains implicit.
For instance, in a critical review of Roger Penrose’s Gödelian argument, Martin Davis (1990. Is Mathematical Insight Algorithmic? Behavioural and Brain Sciences, vol. 13 (1990), pp. 659–660) argues that:
“… There is an algorithm which, given any consistent set of axioms, will output a polynomial equation which in fact has no integer solutions, but such that this fact can not be deduced from the given axioms. Here then is the true but unprovable Gödel sentence on which Penrose relies and in a particularly simple form at that. Note that the sentence is provided by an algorithm. If insight is involved, it must be in convincing oneself that the given axioms are indeed consistent, since otherwise we will have no reason to believe that the Gödel sentence is true”.
Note that the first part of Gödel’s argument in Theorem VI of his 1931 paper is that, if is consistent, then we can mechanically construct a formula—which, syntactically, is of the form —such that:
(i) The formula , when viewed as a string of ‘meaningless’ symbols, does not follow mechanically from the axioms of as the last of any finite sequence of -formulas, each of which is either a -axiom, or a consequence of one or more of the formulas preceding it in the sequence, by the mechanical application of the rules of inference of ;
(ii) For any given numeral —which ‘represents’ the natural number in —the formula , when viewed as a string of ‘meaningless’ symbols, does follow mechanically from the axioms of as the last of some finite sequence of -formulas, each of which is either a -axiom, or a consequence of one or more of the formulas preceding it in the sequence, by the mechanical application of the rules of inference of .
Now, (i) is the standard definition (due to Gödel) of the meta-assertion:
(iii) The -formula is formally unprovable in .
However, under standard interpretations of Alfred Tarski’s definitions of the satisfiability and truth of the formulas of a language under an interpretation , the -formula is true in the interpretation if, and only if, the interpreted relation is instantiationally satisfied in (i. e. for any given element of the interpreted relation can be ‘seen’ to hold in the interpretation).
If we take both and as (as detailed in ‘Evidence-Based Interpretations of PA‘), and take satisfiability in to mean instantiational provability in , we arrive at the formal definition of the truth of the -formula in as:
The -formula is formally true in if, and only if, the formula is provable in whenever we substitute a numeral for the variable in .
Hence (ii) is the standard definition (due to Tarski) of the meta-assertion:
(iv) The -formula is formally true in .
So, by definition, the appropriate interpretation of Gödel’s reasoning (i) and (ii) ought to be:
(v) The -formula is formally unprovable in , but formally true in .
This interpretation also meets Ludwig Wittgenstein’s (Remarks on the Foundations of Mathematics. 1978 edition. MIT Press) requirement that the concept of ‘truth’ in a language must be formally definable, and effectively verifiable, within the language.
As noted by Reuben L. Goodstein (1972. Wittgenstein’s Philosophy of Mathematics. In Ambrose, Alice, and Morris Lazerowitz (eds.), Ludwig Wittgenstein: Philosophy and Language. George Allen and Unwin. pp. 271–86):
“In the realist-formalist controversy in the philosophy of mathematics Wittgenstein’s Remarks offers a solution that is crystal clear and satisfyingly uncompromising. The true propositions of mathematics are true because they are provable in a calculus; they are deductions from axioms by formal rules and are true in virtue of valid applications of the rules of inference and owe nothing to the world outside mathematics.”
However, standard expositions of Gödel’s formal reasoning assert only that:
(vi) The -formula is formally unprovable in , but intuitively true in the standard interpretation of .
They fail to highlight that, actually, (i) and (ii) are both logically entailed by the axioms and rules of inference of , and that, classically, the meta-assertion:
(vii) The -formula is intuitively true in the standard interpretation of .
is both ambiguous and stronger than the meta-assertion:
(viii) The -formula is formally true in .
The ambiguity surfaces in the presence of the Church-Turing Thesis, for (vii), then, implicitly implies that the arithmetical relation is algorithmically decidable as always true in the standard interpretation of , whereas (viii) does not.
Hawking’s provocative pronouncement
“Philosophy is dead”!
Amongst those he managed to successfully provoke were:
What about Hawking’s Thesis?
After we are done with dismissing or rationalising what Hawking said, shouldn’t we also engage in giving at least as serious consideration to the thesis that seemed to have been the backdrop to his pronouncement on the demise of philosophy as a potent tool of enquiry into the truth of scientific propositions?
This is his seemingly prophetic opinion that what we would term as the assignment of objective truth to mathematically expressed scientific propositions will, some day, be based entirely on the evidence provided by simple functional languages (read Turing machines) that are the `fundamental particles’ of Technology.
A seeming contradiction
Seemingly, there is straightaway a contradiction here.
The belief that all of natures laws and natural phenomena can be expressed in the algorithmically determinable truths of mathematical languages can be meta-mathematically expressed by saying that the Church-Turing Thesis must limit human intelligence as it does (by definition) mechanical intelligence.
In other words, even if the Thesis is not formally provable (hence not seen to be true) by a mechanical intelligence, it must be true for a human intelligence!
Apart from this, such a view may also then bind us to the conclusion that at least our universe is characterised by both non-locality and non-determinism (hence possibly the need for multiverses).
Whatever the argument for tolerating multiverses, I have suggested elsewhere that it should not, and perhaps need not, be because we are bound by scientific truths evidenced only by Hawking’s Technology.
What do you think?
Is Hawking’s thesis plausible or contradictory?
If the latter, then:
Does that validate Lucas’ Gödelian argument?
Return to 1: For instance see Chetan R. Murthy, 1991, An Evaluation Semantics for Classical Proofs, Proceedings of Sixth IEEE Symposium on Logic in Computer Science, pp. 96-109, (also Cornell TR 91-1213), 1991.