|
◄ Index |
Section 4 : Does Gödel’s implicit intuitionist meta-thesis demolish strong AI?
Gödel’s proof of undecidability implicitly presumes an intuitionist meta-thesis, and postulates as a Theorem that every recursive relation is representable in his formal system S. We explicitly postulate such a meta-thesis, and use it to construct a simple recursive relation that is not representable in S. Though this does not negate Gödel’s postulation that there are undecidable sentences in consistent formal systems, his particular constructions of such sentences do collapse. In this paper we attempt to highlight significant questions of contemporary interest concerning the value and validity of a Platonist philosophy, the limitations of machine intelligence, and the basis for strong AI that arise if some recursive relation is not formally representable in a consistent S.
1 Gödel’s startling hypothesis
In 1931 Gödel put forth the startling hypothesis - supported by astonishing mathematical constructions and arguments - that ‘… there exist relatively simple problems of the theory of ordinary whole numbers which cannot be decided on the basis of the axioms. … More precisely, there exist undecidable sentences in which, other than the logical constants ‘~ (not)’, ‘Ú (or)’, ‘(x) (for all x)’, ‘= (identical with)’, the only concepts occurring are ‘+ (addition)’ and ‘. (multiplication)’ of natural numbers, and where the prefix ‘(x)’ refers only to natural numbers.’.[1]
2 Significance of Gödel’s hypothesis
The significance of Gödel’s remarkable, yet deceptively simple, claim, lay in the dilemma that philosophers and mathematicians considered themselves to be in as an innocuous 2000 year old paradox was re-constructed by Bertrand Russell and others in logical, mathematical and linguistic settings during efforts[2] to establish stable foundations for scientific thought and reasoning.
The earlier paradox, loosely ascribed to Epimenides, arises obviously if we postulate by definition that a ‘Liar’ sentence, which reads as ‘The ‘Liar’ sentence is a lie’, is a valid sentence within the language in which the sentence is constructed.[3]
Clearly the grammar of an ordinary language, which governs the construction of words and sentences of the language for use as a means of general unrestricted communication, does not contain the specification necessary to prohibit the creation by definition of such self-referential sentences that are devoid of both communicative content and meaning.
The traditional view of this paradox as a minor linguistic anomaly was rudely shaken by Russell’s postulation by definition, within Set Theory, of an equally obvious paradoxical set ‘Russell’ whose elements are all, and only, those sets of the Theory that do not belong to themselves.[4]
To the consternation of mathematicians and philosophers, the axioms and logical rules of inference of Set Theory, which governed the construction of sets for use in a more restricted and precise language of mathematical communication, also did not contain the specification necessary to satisfactorily prohibit the creation by definition of such inconsistent entities - now seen to harbour concealed concepts involving unruly infinite sets.
Classically, definitions had been treated as arbitrary assignments of mnemonically convenient names within a language or Theory for expressing complex reasoning in a compact, more readable, and easier to grasp form.
The paradoxes uncovered a hitherto hidden power of definitions to create inconsistent entities within the language or Theory.
6 Gödel’s constructive formal system S
Gödel thus proposed construction of a formal system S with in-built specifications that would prevent the creation of inconsistent entities through unrestricted definition.[5]
He began by rigorously formalising both the logic and Peano’s axioms of the theory of ordinary numbers in an intuitionistically unobjectionable manner[6] that permitted the creation through definition of only finitely constructive[7] entities.
7 Gödel’s arithmetisation of S
Gödel recognised the significance[8] of the fact that, due to the constructive and rigorously formal character of S, the primitive symbols and well-formed formulas[9] of S, together with all finite sequences of such formulas, formed a well-defined denumerable set.
He could thus put these into a well-defined 1-1 Gödel-numbering correspondence with a proper sub-set of the natural numbers[10], which latter were already represented as a denumerable sub-set of formulas (numerals) within S.
8 Gödel’s remarkable insight
With remarkable insight, Gödel
recognised that if y
is the Gödel-number
corresponding to the formula Y, and x the Gödel-number
corresponding to any finite sequence X of formulas Y1,
Y2, Y3,
…, Yn, then it was possible to constructively define (using recursive arithmetic
functions well-known to mathematicians[11]) a purely numerical relation ‘xBy’ that held if and only if X
was a proof sequence for the formula Y in S[12].
Since ‘xBy’ could clearly be formalised within
S for any
pair of non-negative integers x, y, various meta-statements about S could now be expressed within S.
In an astonishing series of ingenious constructions, Gödel
defined 46 statements of, and meta-statements about, S as purely numerical relations (45 of them recursive)[13]. These could clearly be formalised
within S for any given set of non-negative integer values for the variables contained in them.
9 Gödel’s explicit
thesis
Gödel then postulated in his Theorem V, on the basis of a briefly-sketched argument appealing to induction on the rank of recursive functions[14], the thesis that every recursive function[15] could itself[16] be constructively represented formally as a formula within S in an intuitionistically unobjectionable manner, and so Gödel-numbered.[17]
10 Gödel’s implicit
intuitionist thesis
Now we note that, although the raison d’etre of Gödel’s rigorously defined formal system S lay in the ‘mechanically constructive and intuitionistically unobjectionable nature’ of his meta-reasoning in the meta-theory M of S, reflected strikingly in his arithmetisation of the meta-concept of a formal ‘proof’ in S, Gödel was apparently content to let the ‘mechanically constructive and intuitionistically unobjectionable nature’ of ‘provable’ open formulas (infinitely-compound sentences) of his formal system S remain implicit[18].
The question we now consider is whether Gödel’s formal system S, and its meta-theory M, are as completely defined as needed to reflect Gödel’s explicitly stated ‘mechanically constructive and intuitionistically unobjectionable’ intentions[19].
We therefore see how we can explicitly capture the essence of the ‘constructive and intuitionistically unobjectionable nature’ of the concept implicit in the ‘provability’ of an open formula (infinitely-compound sentence) of S.
One alternative would be to specify as Gödel’s Implicit Intuitionist Meta-thesis, in the meta-theory M of S, that a formula be provable in S if and only if it is provable in S for all non-negative integer (numeral) values of the variables contained in it.
If R(x) is a recursive formula (of a single variable), for
instance, and we denote the meta-statement ‘R(x) is a provable
formula of S’ by
‘├S R(x)’, the above would meta-postulate that :
├S R(x) ≡M (n)├S R(n).[20]
Such a meta-thesis ensures that
the provable open formulas of S, starting with
the axioms of S, translate into
denumerably-many statements under interpretation, i.e. it acts as a meta-axiom
for identifying and determining the denumerable models of S satisfying Peano’s axioms.
We conjecture that the absence of such specification results in the formal system S being inadequately defined, and that this permits the surreptitious entry of arguably ill-defined, Platonistic, ‘elements’ into S, such as those leading to a paradox, since the domain of ‘x’ need not then be denumerable under interpretation.
More importantly in the present instance, we note that the representations in S of some, if not all, of Gödel’s 46 definitions [Gödel 1931: p17-221] - such as those of, for instance, ‘x/y’ of divisibility, Prim(x) of primality and ‘Bew(x)’of provability (equivalent within S to the meta-concept ‘├S’ in the meta-theory M of S) - cannot be assumed to be well-defined over an extended, transfinite, range, since these are defined[21] only through an interpretation over the non-negative integers.
Thus we now consider whether Gödel’s definitions and reasoning are valid, and significant, in those interpretations of his formal system S that are denumerable domains, and where some thesis such as Gödel’s Implicit Intuitionist Meta-thesis holds.
11 Gödel’s undecidable proposition
We note that Gödel
next considered the purely numerical recursive relation defined by ‘~ [ x B [ Sb ( y : (19, z(y)) ) ] ]’[22], which held if and only if :
‘The formula (sequence) X, whose Gödel-number is x, is not a proof-sequence[23] in S of the formula (n-ary predicate[24]) obtained from the formula (n-ary predicate) Y, whose Gödel-number is y, when we substitute the numeral z(y)[25] for the formula (free variable) whose Gödel-number is 19[26] in the formula (n-ary predicate) Y whose Gödel-number is y.’[27]
By Gödel’s thesis §9, this relation could be constructively represented formally by some formula (binary predicate) Q within S in an intuitionistically unobjectionable manner, and so Gödel-numbered by some constructible number q.
Applying closure to Q, Gödel
then considered the purely numerical relation defined by ‘(x) [ ~ [ x B [ Sb ( y : (19, z(y)) ) ] ] ]’[28].
If Q is a formula (binary predicate) of S, this relation can be constructively represented formally by some formula (class expression) P within S in an intuitionistically unobjectionable manner, and so Gödel-numbered by some constructible number p.
After suitable substitutions, Gödel finally considered the purely numerical relation defined by ‘(x) [ ~ [ x B [ Sb ( q : (19, z(p)) ) ] ] ]’[29].
If P is a formula (class expression) of S, then clearly this relation can also be constructively represented formally by some formula (sentence[30]) G within S in an intuitionistically unobjectionable manner.
Gödel then showed by simple reasoning that, although the relation defined by ‘(x) [ ~ [ x B [ Sb ( q : (19, z(p)) ) ] ] ]’ clearly holds, G is an undecidable sentence in S since neither G nor ~G are provable in a consistent S.[31]
12 The path Gödel ignored
Following Gödel’s reasoning, we now
consider the purely numerical recursive relation ‘~ [ x B [ Sb ( q : (19, z(q)) ) ] ]’, which holds if and only if :
‘The formula (sequence) X, whose Gödel-number is x, is not a proof-sequence in S of the formula (n-ary predicate) obtained from the formula (binary predicate) Q, whose Gödel-number is q, when we substitute the numeral z(q) for the formula (free variable) whose Gödel-number is 19 in the formula (binary predicate) Q whose Gödel-number is q.’[32]
If Q is a formula (binary predicate) of S, then this relation too can be constructively represented formally by some formula (class expression) R within S, and so Gödel-numbered by some constructible number r.
It is easy now to see that the path Gödel chose diverged at this point by ignoring the Implicit Intuitionist Meta-thesis underlying his reasoning since, by arguments identical to those showing the undecidability of G in S, we arrive at the inconsistency in the meta-theory M of S :
R is provable in S →M R is not provable in S, and
R is not provable in S →M R is provable in S.[33]
13 Was Gödel wrong?
Clearly, if Gödel’s Implicit Intuitionist Meta-thesis holds, then his Theorem V is invalid. Since Gödel did not provide[34] a rigorous proof of his thesis that every recursive function could be constructively represented formally in S in an intuitionistically unobjectionable manner, and so Gödel-numbered, it is not prima facie clear where, or even whether, his reasoning was wrong.
However, his argument ran as follows. If (x+y) is the recursive function of rank two[35] defined by ‘sum(x, 0) ≡ x; sum(x, y+1) ≡ sum(x, y)+1’, then it can be imitated[36] in the formal system S by ‘sum(x, 0) ≡ x; sum(x, Ny) ≡ Nsum(x, y)’, where ‘Nx’ is the successor function[37] of rank one in S.
14 ‘sum(x, y)’
cannot be expressed directly in S
Now, if we define N [y]0 ≡ y so that, for example, N [3]0 ≡ NNN0 and ‘sum(x, N[y]0)’ denotes the formal function ‘sum(x, y)’, we see that sum(x, y) ≡ N [y]x.
For any given k, sum(x, k) is obviously expressible formally in terms of only the primitive symbols ‘N’ and ‘x’ of S. Also, for a given k, the unique Gödel-number rk of the formal expression corresponding to sum(x, k) is rk = 22. 32. 52. 72. 112. … pk2. pk+116, by Gödel’s 1-1 correspondence, where pi is the i’th prime.[38]
However, for a variable y, we clearly cannot express sum(x, y) - or the equivalent N[y]x - in terms of only the primitive symbols of S[39]. Similarly, for a variable y, ry too cannot be enumerated so as to yield a unique Gödel-number r of a formal expression in S that corresponds to sum(x, y).
So a formal expression consisting of only the primitive symbols of S and corresponding to the recursive function ‘sum(x, y)’, i.e. ‘x+y’, cannot be constructively built up[40] from the recursive formal function ‘Nx’ by formally ‘imitating’[41] the operations of substitution or recursive definition within S.[42]
15 Platonist creation through definition
Now Gödel’s thesis was that, from the Gödel-number r1=22.316 of ‘Nx’[43], one could obtain a unique Gödel-number r for a formal expression consisting of only the primitive symbols of S that corresponds to the formal recursive function ‘sum(x, y)’, where r is constructively defined by the purely formal structure of the formal expression corresponding to ‘sum(x, y)’.[44]
Thus Gödel’s thesis critically depends on the indirect existence through definition[45] of a formal expression in terms of only the primitive symbols of S that is formally equivalent to the formal recursive function ‘sum(x, y)’.
Such existence through definition is strongly reminiscent of the Platonist postulations, and creations by definition, of the anomalous ‘Liar’ sentence and ‘Russell’ set.
Despite the absence of a rigorous proof in his paper in support of his postulation by definition, Gödel, reportedly a ‘…very strong Platonist.’[46], was apparently comfortable[47] that this lacuna in his reasoning would not yield an inconsistency.[48]
Now formal number theory, such as developed in Mendelson[49], does attempt to justify Gödel’s reasoning by using the stratagem of a ‘Gödel β-function’[50]. However, this only permits sequences of determinate, if undetermined, length to be represented by formulas of a formal system S', where addition is an undefined primitive symbol.[51]
Despite Mendelson’s claim - also without a rigorous proof[52] - the Gödel β-function cannot be used to validly construct a formula strongly[53] representing a primitive recursive function, which is essentially an infinite sequence of indeterminate length.
Moreover, as we show in detail in companion papers[54], inconsistencies arise not only in Gödel’s formal system as above, but also in Mendelson’s formal system out of the postulation that every primitive recursive function can be strongly represented in these systems.
17 Why did Gödel choose the path he chose?
The questions arise :
a) How could Gödel overlook straightforward reasoning leading to the kind of inconsistency that he was actually trying to avoid, and which is obvious, and put his faith in, and authority behind, the subtlety of an argument that is anything but obvious?
b) What are the insights that his reasoning has given to a generation of mathematicians, scientists and philosophers, which are so rich and powerful that the obvious remains obscured behind the obscure?
c) Are any of the developments directly or indirectly fueled by Gödel’s work significantly affected - or diminished - if his specific conclusions collapse?
18 Gödel’s Theorems from a wider perspective
There can be no doubt that had Gödel not chosen[55] to focus entirely on and develop the path that he did follow, he would have found the reasoning leading to an inconsistency in his system S. So why did he stray, and stay, off this path?
Considering Gödel’s strongly Platonist philosophy, his interpretation of the significance of his Theorems to scientific thought, which may have influenced the direction he took, could have been that they appeared to him to postulate in principle the existence of abstract entities whose essence cannot be totally grasped by us, in some ‘absolute’ sense, even theoretically.
An obvious parallel would be the development of the various Quantum Theories in Physics, culminating in Schroedinger’s work and Heisenberg’s Uncertainty Principle, postulated about the same time, whose philosophical implications indicated that there exist physical entities whose essence cannot be totally grasped by us, in some ‘absolute’ sense, even theoretically.[56]
However, although Schroedinger’s work and Heisenberg’s postulation continue to be part of the founding bedrock of the physical sciences, and a significant factor in the continuing enquiry as to the relationship between Intelligence and Cosmos, it is debatable whether the postulation of a parallel principle underlying Gödel’s Theorems retains any meaning or content in the absence of a Platonist platform lying beyond personal choice.
19 The relative significance of Gödel’s reasoning
If we assess the significance of the above two anomalous sentences and Gödel’s sentences within their respective disciplines, we see that :
a) ‘The ‘Liar’ sentence is a lie’ can be seen as :
* linguistically significant, since it is a declarative sentence that has a well-defined linguistic ‘form’, but no communicative ‘content’,
* logically significant, since, being neither true nor false, it violates the dictates of a two-valued logic and highlights the essential inconsistency of any ordinary language used as a means of general, unrestricted, communication,
* philosophically significant, since it characterises ‘intelligence’ by the ability to perceive a subjective ‘meaning’ in an objective ‘form’, and to recognize, and ‘meaningfully’ utilise, a sub-language of ‘ordered’ communication whilst operating within an essentially inconsistent ‘disorderly’ language.
b) The sentence ‘The ‘Russell’ set belongs to itself.’ can be seen as :
* mathematically significant, since it can be expressed in a well-defined mathematical ‘form’;
* logically significant, since, being neither true nor false, it violates the dictates of a two-valued logic and highlights the essential inconsistency of unrestricted set theory when used as a means of mathematical communication;
* ontologically significant, since it establishes the power to construct, by postulating through definition the (Platonist?) ‘existence’ of, an inconsistent element[57] in an abstract system;
* philosophically also significant otherwise, since it characterises ‘intelligence’ by the ability to construct and operate consistently within an essentially inconsistent abstract system.
c) Gödel’s assertion that in every formal system S there is a formula G with Gödel-number g which translates as ‘The formula G with Gödel-number g is not provable in S.’ can be seen as :
* logically significant, reflecting an ‘inadequacy’ in definition of the formal system S, and highlighting the role of, and need for, meta-specifications regarding the nature of the permissible range for the variables of the system;
* ontologically significant as this also constructs, by postulating through definition the (Platonist?) ‘existence’ of, an inconsistent element[58] of an abstract system;
d) The fact that there are recursive relations that cannot be represented formally in ‘constructive’ formal systems can be seen as :
* philosophically significant since it indicates that formal-system based Artificial Intelligence (AI) may be limited in its ability to ‘imitate’ natural intelligence.
20 So what does Gödel’s reasoning actually achieve?
Gödel's thesis was that there are true sentences that are expressible formally but not provable. If there are recursive functions that are not expressible formally, Gödel's sentence would still be true, but not necessarily expressible formally, and still not provable. So the collapse of his theorem need not negate his thesis[59] - only his particular proof of it and the part postulating the formal expressibility of every recursive function.
However, his reasoning does establish that there are decidable[60] recursive relations which cannot be constructively expressed formally within a consistent system in an intuitionistically unobjectionable manner.
Can we then conjecture that the development of significant AI may involve the challenge of designing machines with an inconsistent logical basis, and a ‘psycho-cybernetic’ ability to recognise illogical directions, possibly through distributed computing (which raises the question of whether any single entity can develop intelligence)?
21 Addressing Platonism : What is Mathematics?
Regarding the question of ‘existence’ and Platonism, a strikingly curious feature of the paradoxes is that they do not seriously threaten, or even partially paralyse, any of the sciences. They only inconvenience a small body of purists in the logical and ontological area.
Could this be because scientists are unconsciously familiar with their own inconsistent creations, and can co-exist with, and function effectively despite, them! Could the issue of abstract existence really then involve the philosophical question of what, precisely, is Mathematics?
Is Mathematics an abstract Platonist universe in itself, an ‘internal’ one with contents ‘reflecting’ an ‘external’ universe, where the various mathematical disciplines contribute jointly and severally to the contents of this abstract world?
Or, is Mathematics a collection of increasingly precise, increasingly powerful and continuously evolving languages (such as algebra, number theory, etc.), developed ‘internally’ through distinctively different dialects (such as modular forms, analytic methods and summation formulas, etc.), for communicating experiences and content ‘relating’ to an ‘external’ universe?
In practice, at a personal level, it does appear that we address and answer the above queries sub-consciously, and quite inconsistently, reflecting both situational needs and conveniences, determined overall by issues of personal predilection and individual taste.
We appear to opt for the Platonist viewpoint as the more rewarding when we need to ‘internally’ build up a 'mental picture' that we would loosely term as our 'understanding' of mathematical structures within ourselves; the linguistic view where we need or desire to ‘externally’ communicate our 'understanding' and 'vision' to others.
If this is significantly so, do we really need to commit to one over the other? Could our present personal predilections and individual tastes, which strongly determine our individual output and effectiveness but generally reflect powerful influences of the environment we nurture and are nurtured in, be overly biased towards the Platonist viewpoint?.
Could such a bias be detrimental to the unleashing of the full power and potential of individual human creativity - whether in expression or in discovery? Could a bias be addressed and balanced at the ‘system’ level, by balancing the way we approach, follow, practice and teach the various disciplines constituting mathematics?
Instead of addressing the question of what there is classically (i.e. seek the totality of existence in an ‘objective’, absolute abstraction), does Gödel's reasoning indicate that we can as significantly ask the question of how, in a given situation, we should view what there is (i.e. seek only a means of expressing partially, through ‘subjective’, relative abstraction, that which we believe to ‘exist’ externally)?
Although Gödel himself believed that he had significantly established the existence of formally undecidable sentences, does his reasoning actually establish, far more significantly, the limitations of machine intelligence; and does it in fact weaken - if not demolish - the basis for both Platonism and strong AI by giving substance to some of the above queries? [61]
Notes (Why05ct.doc : 4/7/01 7:17:17 AM)
[1] That Gödel intention of reasoning in a ‘mechanically constructive and intuitionistically unobjectionable’ way requires the range of the variables of the formal system S to be denumerable under interpretation is reflected here. [Gödel 1931: p6]
[2] Such as Russell and Whitehead’s attempt to equate mathematics and logic in their monumental work Principia Mathematica.
[3] Is the ‘Liar’ sentence true or false?
[4] Is the ‘Russell’ set a member of the ‘Russell’ set?
[5] Gödel developed the formal system S as ‘ … essentially the system which one obtains by building the logic of PM (Principia Mathematica) around Peano’s axioms (numbers as individuals, successor relation as undefined primitive concept).’ [Gödel 1931 : p10]
[6] i.e. without use, vaguely speaking, of existence proofs such as arguments that depend, for example, on the use of the Law of the Excluded Middle. [Gödel 1931 : p26 footnote 45a]
[7] i.e. entities constructible by a finitely terminating procedure. [Gödel 1931 : p26 footnote 45a].
[8] See also Anand 2000 : chapter 4.
[9] Gödel defined the primitive symbols of S as consisting of various constants and variables; combinations of certain symbols as terms; and combinations of certain symbols and terms as the various types of formulas of S. [Gödel 1931 : p11]
For convenience of exposition in translations, we sometimes
use the word ‘formula’ to also refer to any formal expression consisting of a
finite sequence of the primitive symbols of S, or - as
here - to a finite sequence of formal expressions.
[10] Gödel described in detail how every primitive symbol of S, every formal expression consisting of a finite sequence of such symbols of S, and every sequence of formal expressions can be arithmetised and correlated uniquely to some natural number - which we define as the G