universal, formulas, statements, Chaitin, sentences, theorem, consistent, provable, Goldbach conjecture, Berry paradox, Goldbach, conjecture, paradox, Berry, incompleteness, Chaitin theorem
Back to title page.
Left |
Adjust your browser window |
Right |
Let us consider the famous Goldbach's Conjecture from 1742 by Christian Goldbach (1690-1764): every even number greater than 2 can be expressed as a sum of two prime numbers. For example (the really interesting numbers are shown in bold),
4=2+2, 6=3+3, 8=5+3, 10=5+5, 12=7+5, 14=11+3, 16=13+3, 18=13+5, 20=17+3, 22=19+3, 24=19+5, 26=23+3, 28=23+5, 30=23+7, 32=29+3, 34=31+3, 36=31+5, 38=31+7, 40=37+3, 42=37+5, 44=41+3, 46=43+3, 48=43+5, 50=47+3, 52=47+5, 54=47+7, 56=53+3, 58=53+5, 60=53+7, 62=59+3, 64=61+3, 66=61+5, 68=61+7, 70=67+3, 72=67+5, 74=71+3, 76=73+3, 78=73+5, 80=73+7, 82=79+3, 84=79+5, 86=83+3, 88=83+5, 90=83+5, 92=89+3, 94=89+5, 96=89+7, 98=79+19, 100=97+3, 102=97+5, 104=97+7, 106=103+3, 108=103+5, 110=107+3, 112=109+3, 114=109+5, 116=113+3, 118=113+5, 120=113+7, 122=109+13, 124=113+11, 126=113+13, 128=109+19, 130=127+3, 132=127+5, 134=131+3, ...
See also:
Puzzle 82.- The Goldbach's Comet by www.primepuzzles.net
Goldbach Conjecture Research by Mark Herkommer
Fractal in the statistics of Goldbach partition by Wang Liang, Huang Yan, Dai Zhi-cheng
Eric W. Weisstein. "Goldbach Conjecture." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GoldbachConjecture.html
Assume, you are a Platonist believing that Goldbach's Conjecture is, "in fact", true. I.e. if you take any even number n, it can be expressed as a sum of two primes. If it can, you can determine these two primes p1+ p2 = n simply by trying n = (n-3)+3, n=(n-5)+5, n=(n-7)+7, n=(n-11)+11, etc. up to n=k+k. Any particular true equality p1+ p2 = n, i.e.
(1+1+...+1) + (1+1+...+1) = (1+1+...+1)
p1 times ------ p2 times ------- n times
can be proved in PA (see Exercise 3.4a).
Let Go(x) be a formula expressing in PA the following (computable) predicate go(x):
"If x is an even number greater than 2, then x is a sum of two primes",
for example,
Ey(y<x & x=y+y) & 2<x ->Ep1Ep2(p1<x & p2<x & prime(p1) & prime(p2) & x=p1+p2),
where:
a<b is a shortcut for Ec(a+c+1=b), and
prime(z) is a shortcut for ~EuEv(u<z & v<z & z=u*v).
Formula Go(x) contains only bounded quantifiers. As we know from Exercise 3.4b, for each natural number n, if Go(n) is true, then PA proves Go(n) (n is the numeral representing the number n).
Now, Goldbach's Conjecture can be represented as the formula AxGo(x).
Thus, we have the following situation. If Goldbach's Conjecture is true, then, for each natural number n, PA proves Go(n). Could we conclude from this that PA |- AxGo(x), i.e. that PA proves Goldbach's Conjecture?
In general, no. Because, "for each n, PA |- Go(n)" means that there is an infinite sequence of proofs, a separate proof for each formula Go(n). Could we hope to convert this infinite sequence into a single finite proof of the formula AxGo(x)?
In general, no. For example, Goedel's self-referencing formula G, used in the incompleteness proof of PA, asserts "I'm not provable in PA". It is equivalent to the formula Ay~PRF(G, y), where the formula PRF(x, y) express the predicate "y is a PA-proof of x" (more precisely, "y is Goedel number of a PA-proof of the formula having Goedel number x"). As we know from Section 5.3, if PA is a consistent theory, then G cannot be proved in PA, i.e. the formula ~PRF(G, n) is true for each n (G is the Goedel number of G). Hence, for each n, PA |- ~PRF(G, n). Could we conclude from this that PA |- Ay~PRF(G, y), i.e. that PA proves Goedel's formula G? No, because this would mean that PA is inconsistent! Hence, if PA is a consistent theory, then the infinite sequence of PA-proofs of the formulas ~PRF(G, n) cannot be converted into a single finite PA-proof of the formula Ay~PRF(G, y).
On the other hand, let us assume that Goldbach's Conjecture is false. Then there is an even number n>2, which cannot be expressed as a sum of two primes. Then, as we know from Exercise 3.4b, since the formula ~Go(x) contains only bounded quantifiers, we can prove in PA the formula ~Go(n). Then, of course, PA |- ExGo(x), and PA |- ~AxGo(x). Hence, if Goldbach's Conjecture is false, then PA "proves this fact".
And thus, if we could prove that PA cannot prove that Goldbach's Conjecture is false, then we would have a proof... that Goldbach's Conjecture is true! Since
"PA cannot prove that Goldbach's Conjecture is false"
is equivalent to
"PA + Goldbach's Conjecture is a consistent theory".
Hence, if we could prove that Goldbach's Conjecture is consistent with the axioms of PA, then we would have a proof that Goldbach's Conjecture is true!
The only specific property used in the above chain of reasoning, is the following: for all n, if Go(n) is false, then PA |- ~Go(n), so, a more general formulation of the above statement should be possible. Let us try to produce it.
Let T be any formal theory in the language of PA, and M - a fundamental theory. We will use M as a meta-theory of T.
F(x) is a formula containing exactly one free variable x.
PRT(y) is a formula intended to assert that "the formula having the Goedel number y is provable in T".
SUB(x, y, z) is a formula representing in PA the so-called substitution function (see Section 5.2):
sub(x, y) = "Goedel number of the formula obtained from the formula having the Goedel number x by substituting the numeral y for all of its free variables" (if x is not a Goedel number of a formula, then let sub(x, y)=0).
Suppose, T and M are powerful enough in the sense that
M proves: "For all natural numbers n, if ~F(n), then T |- ~F(n)".
More precisely (~F is the Goedel number of the formula ~F),
M |- An(~F(n) -> Ay(SUB(~F, n, y)->PRT(y))) .
Hence,
M |- An(~Ay(SUB(~F, n, y)->PRT(y)) -> F(n)), -------------- (*)
i.e. M proves that for all n, if T does not prove ~F(n), then F(n) is true.
(1) Suppose, T, M and PRT satisfy the following uniform derivability condition:
M proves: "For all n, if T |- D(n), then T |- ExD(x)".
More precisely (D and ExD(x) are Goedel numbers of the formulas D(x), ExD(x)),
M |- An[Ay(SUB(D, n, y)->PRT(y)) -> PRT(ExD(x))].
Hence,
M |- An[~PRT(ExD(x)) -> ~Ay(SUB(D, n, y)->PRT(y))],
and,
M |- ~PRT(ExD(x)) -> An[~Ay(SUB(D, n, y)->PRT(y))],-------------- (**)
i.e. M proves that, if T does not prove ExD(x), then for all n, T does not prove D(n).
(2) Suppose, T, M and PRT satisfy Hilbert-Bernays-Loeb derivability conditions (see Section 5.4).
Now, from (*) and (**) we obtain directly that
M |- ~PRT(Ex~F(x)) -> AnF(n).
Since T |- Ex~F(x) -> ~AxF(x), then, by (3), we obtain that
M |- PRT(Ex~F(x)) -> PRT(~AxF(x)),
M |- ~PRT(~AxF(x)) -> PRT(Ex~F(x)),
and
M |- ~PRT(~AxF(x)) -> AnF(n) ------------ (***).
Thus, we have proved the following
Theorem 6.7.1 (Author(s)? Folklore?). Suppose, T is any formal theory in the language of PA, M is a fundamental theory, and they satisfy the above-mentioned derivability conditions (1, 2). If, for the formula F(x) containing exactly one free variable x,
a) M proves: "For all natural numbers n, if ~F(n), then T |- ~F(n)",
b) M proves that ~AxF(x) cannot be proved in T,
then M proves AxF(x).
Corollary 6.7.2 (Author(s)? Folklore?). Suppose, T is any formal theory in the language of PA, M is a fundamental theory, and they satisfy the above-mentioned derivability conditions (1, 2). If, for the formula F(x) containing exactly one free variable x,
a) M proves: "For all natural numbers n, if ~F(n), then T |- ~F(n)",
b) M proves that T+AxF(x) is a consistent theory,
then M proves AxF(x).
Proof. "M proves that T+AxF(x) is a consistent theory" - what, precisely, does it mean? The formula Con(T+AxF(x)) can be defined as "T does not prove AxF(x)->0=1", i.e. as ~PRT(AxF(x)->0=1). Since T |- ~AxF(x) -> (AxF(x)->0=1) (Axiom L10), then, by (3), we obtain that
M |- PRT(~AxF(x))->PRT(AxF(x)->0=1),
M |- Con(T+AxF(x)) -> ~PRT(~AxF(x)).
By (***),
M |- Con(T+AxF(x)) -> AnF(n).
Q.E.D.
Corollary 6.7.3 (Author(s)? Folklore?). Suppose, T is any formal theory in the language of PA, M is a fundamental theory, and they satisfy the above-mentioned derivability conditions (1, 2). If
a) M proves: "For all natural numbers n, if ~Go(n), then T |- ~Go(n)",
b) T + Goldbach's Conjecture is a consistent theory,
then M proves Goldbach's Conjecture.
Proof. Immediately, from Corollary 6.7.2.
Corollary 6.7.4 (Author(s)? Folklore?). Suppose, M is a fundamental theory, PA and M satisfy the above-mentioned derivability conditions (1, 2). If M is powerful enough to prove that PA + Goldbach's Conjecture is a consistent theory, then M proves Goldbach's Conjecture.
Proof. As we established above,
"For all natural numbers n, if ~Go(n), then PA |- ~Go(n)."
These verifications can be formalized in PA:
PA |- An(~Go(n) -> Ay(SUB(~Go, n, y)->PRT(y))).
Hence, since M is a fundamental theory, then, by Corollary 6.7.3, Q.E.D.
According to Corollary 6.7.3, instead of PA, we could use any weaker axiom system T such that for all natural numbers n, if ~Go(n), then T proves ~Go(n). Thus, if we could prove that Goldbach's Conjecture is consistent with the weakest known of such axiom systems, then we would have proved that Goldbach's Conjecture is true! The weaker the system T, the easier should be the consistency proof of T + Goldbach's Conjecture? Yes, but - the weaker the system T, the more difficult becomes proving of "for all natural numbers n, if ~Go(n), then T |- ~Go(n)". This proof is very easy for PA, but the consistency proof of PA + Goldbach's Conjecture seems to be very difficult...
Strange and/or crazy situation? A kind of paradox?
Note. The conclusion of Corollary 6.7.4 does
not apply to the Twin Prime Conjecture:
AxEp (p>x & (p, p+2) is a twin pair).
The negation of it means that there is a number n such
that
Ap (p>=n -> (p, p+2) is not a twin pair).
If one proves that Twin Prime Conjecture (or its negation) does
not create contradictions, this does not yield a proof of this
conjecture (or its negation).
Exercise 6.8.1 (for smart students). If one proves that Riemann Hypothesis (or its negation) does not create contradictions, does this yield a proof of this conjecture (or its negation)?
Further reading:
Online comments by William G.Dubuque at http://www.math.chalmers.se/~bo/internetguiden/listexempel.html#9
Kemeny, J. G. "Undecidable Problems of Elementary Number Theory." Math. Ann. 135, 160-169, 1958.
Kreisel's Conjecture - see: Eric W. Weisstein. "Kreisel Conjecture." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/KreiselConjecture.html
Goedel's Incompleteness Theorem was - in a sense - "inspired" by the Liar's Paradox. The idea that Berry's Paradox could inspire an incompleteness theorem, which could be, in a sense, stronger than Goedel's theorem is due to Gregory J.Chaitin. He tells in his 1993 lecture at the University of New Mexico that in 1974 he tried to check the reaction of Goedel himself to this idea. Unsuccessfully.
In this section, a purely syntactical version of Chaitin's Theorem will be proved. I.e. neither "semantical soundness" of the theories in question, nor even their syntactical consistency will be assumed.
In its classical form, Berry's Paradox sounds as follows. Let us consider the following phrase, consisting of fourteen English words:
The first natural number, which cannot be defined by using under fifteen English words.
Thus, "the first natural number, which cannot be defined by using under fifteen English words" can be defined by using fourteen English words!
Unfortunately, very little can be found on the web about the author of this paradox. According to Berry paradoxWikipedia: "Bertrand Russell, the first to discuss this paradox in print, attributed it to G. G. Berry, a librarian at Oxford's Bodleian library." And according to Vicious circleBritannica the full name of G. G. Berry was George Godfrey Berry.
The above-mentioned Russell's 1906 paper:
B. Russell. Les paradoxes de la logique. "Revue de Metaphysique et de Morale", 1906, 14, pp.627-650.
Of course, Berry's Paradox is not the only paradoxical thing that can be expressed "by using English words". Some people try "solving" paradoxes by introducing language rules allowing to avoid them. Still, on the other side, each paradox contains its specific creative potential. For example, by formalizing the Liar's Paradox one can prove Goedel's Incompleteness Theorem (see Section 5.3). Which kind of incompleteness theorems could be derived from Berry's Paradox?
The proof below was adapted from the paper:
Panu Raatikainen. On Interpreting Chaitin's Incompleteness Theorem. Journal of Philosophical Logic, 1998, vol. 27, pp. 569-586 (available online).
Let us consider Turing machines (TMs) that are working without input data, and that, when halting, generate some natural number x. Such a TM can be considered as a "definition" of the number x, and thus, in this way, we can try to obtain a version of Berry's Paradox.
Let us consider an enumeration of the above-mentioned TMs:
TM0, TM1, TM2, ..., TMn, ..., -------------------- (1)
such that:
a) The following predicate h(x, y, t) is computable (i.e. "recursive"):
h(x, y, t) = "TMy halts in t steps and generates the number x".
b) Kleene's Fixed Point TheoremWikipedia holds: for any computable (i.e. "recursive") function f one can construct an index e such that TMf(e) does exactly the same that does TMe.
According to Representation Theorem, there is a formula H(x, y, t) expressing the predicate h(x, y, t) in PA (i.e. first order arithmetic).
For the number x, if y is the minimum index such that TMy halts and generates x, then, if you wish, you can think of y as the Kolmogorov complexityWikipedia of x, and put this as K(x)=y.
The formula
C(x, y) = Ey0Et(y0<=y & H(x, y0, t))
asserts that "x is generated by some TM with an index <=y". If you wish, you may put this as K(x)<=y.
C(x, y) is a Sigma1-formula, i.e. it "expresses" an effectively (i.e. recursively) denumerable predicate.
The formula ~C(x,y) asserts that "x is not generated neither by TM0, nor by TM1, ..., nor by TMy. If you wish, you may put this as K(x)>y. (~C(x,y) is a Pi1-formula.)
Of course, for any fixed index c, the formula C(n, c) may be true only for a finite number of n-s (i.e. only for numbers generated by TM0, TM1, TM2, ..., TMc, if such numbers exist at all). This simple fact can be proved in PA:
PA proves: AcEn0An(C(n, c) -> n<=n0), or:
PA proves: AcEn0An(n>n0 -> ~C(n, c)). ------------------ (2)
Secondly, if for some numbers n, c, the formula C(n, c) is true, then, for any d>=c, C(n, d) is true as well. This simple fact also can be proved in PA:
PA proves: AnAcAd(d>=c ->(C(n, c) -> C(n, d)), or:
PA proves: AnAcAd(c<=d -> (~C(n, d) -> ~C(n, c)). --------------- (3)
Now, we can try modeling Berry's Paradox. Namely, let us try to define a TM which is trying to generate a number that can't be generated by a TM of this "size". I.e. let us try to define a TMe which is trying to generate a number that can't be generated neither by TM0, nor by TM1, ..., nor by TMe.
How obtain a TMe, the definition of which refers to its index e? Of course, by applying Kleene's Fixed Point Theorem. First, we will, having an arbitrary number c, define a TMd which is trying to generate a number n that can't be generated neither by TM0, nor by TM1, ..., nor by TMc. Here, by construction, d will be computable from c as some (i.e. recursive) function f(c). Then, by Kleene's Fixed Point Theorem, one will construct an index e such that TMe does exactly the same that does TMf(e). Hence, TMe will be trying to generate a number n that can't be generated neither by TM0, nor by TM1, ..., nor by TMe.
Now, to instead of "can't be generated", we will introduce "can't be generated, according to theory T", where T is any fundamental theory (i.e. a formal theory covering first order arithmetic).
Thus, given a number c, we define the following TMf(c): scan, one by one, all the T-proofs, if some of these proofs proves, for some number n, that n can't be generated neither by TM0, nor by TM1, ..., nor by TMc, then output this n as the result.
In other words: given a number c, we define the following TMf(c): scan, one by one, all the T-proofs, if some of them proves the formula ~C(n, c) for some number n, then output this n as the result.
Now, by Kleene's Fixed Point Theorem, one can construct an index e such that TMe does exactly the same that does TMf(e). Hence, TMe scans, one by one, all the T-proofs, if some of them proves the formula ~C(n, e) for some number n, then TMe outputs this n as the result.
Of course, the index e depends on the theory T: e = eT.
Thus, we have a particular Turing machine TMe (depending on T). Does TMe halt?
1. TMe halts in some t steps and outputs some number n, if and only if there is a T-proof of the formula ~C(n, e):
T proves: ~C(n, eT).
But, simultaneously, the fact, that TMe halts in t steps and outputs the number n, can be proved in PA:
PA proves: H(eT, n, t).
Hence, also,
PA proves: Ey0Et(y0<=eT & H(n, y0, t)), i.e.
PA proves: C(n, eT).
Since T covers PA, then also
T proves: C(n, eT).
Thus, if TMe halts, then T is an inconsistent theory.
2. If, otherwise, TMe does not halt, then T proves ~C(n, eT) for NONE of the numbers n. Is this something bad? From (2) we know that
PA proves: En0An(n>n0 -> ~C(n, eT)),
i.e. PA (and T) proves that ~C(n, eT) is true for all n, except for at most a finite number of exceptions. But T cannot prove ~C(n, eT) for NONE of the numbers n!
Thus, if we denote ~C(x, y) by K(x, y), then we have proved, in fact, the following
Chaitin's Theorem. In the language of PA,
there is a Pi1-formula K(x, y) such that:
a) PA proves: AcEn0An(n>n0
-> K(n, c)), i.e. that, for any fixed c,
K(n, c) is true for all n, except for a finite number of
exceptions.
b) For any fundamental formal theory T one can construct a
number eT such that if, for some number n, T proves K(n, eT), then T is inconsistent.
Corollary 1. There is a Pi1-formula K(x,y) such that PA proves AcEn0An(n>n0 -> K(n, c)), but for any consistent fundamental formal theory T one can construct a number eT such that T can prove K(n, eT) for none of the numbers n.
Since, for infinitely many numbers i, TMi does not halt, the formula K(n, n) must be true for infinitely many numbers n. This simple fact can be proved in PA:
PA proves: AmEn (n>m & K(n, n)).
But, if T is consistent, it can prove K(n, n) only for a finite number of n-s. Indeed, T cannot prove K(n, n), if n>=eT. Hence,
Corollary 2. There is a Pi1-formula K1(x) such that PA proves that K1(n) is true for infinitely many n-s, but any consistent fundamental theory T can prove K1(n) only for a finite number of n-s.
Or, if you wish to put ~C(x, y) as K(x)>y, then you may have a more traditional formulation of
Chaitin's Theorem. In the language of PA,
there is a Pi1-formula K(x)>y such that:
a) PA proves: AcEn0An(n>n0
-> K(n)>c), i.e. that, for any fixed
c, K(n)>c for all n, except for a finite number of exceptions.
b) For any fundamental formal theory T one can construct a
number eT such that if, for some number n, T proves K(n)>eT, then T is inconsistent.
Corollary 1. There is a Pi1-formula K(x)>y such that PA proves AcEn0An(n>n0 -> K(n)>c), but for any consistent fundamental formal theory T one can construct a number eT such that T can prove K(n)>eT for none of the numbers n.
Corollary 2. There is a Pi1-formula K(x)>x such that PA proves that K(n)>n is true for infinitely many n-s, but any consistent fundamental theory T proves K(n)>n only for a finite number of n-s. If we wish to interpret K(n)>n as "n is a random bit-string", then we can obtain the following beautiful thesis: PA proves that there are infinitely many random bit-strings, but any consistent fundamental theory T can prove the randomness of only a finite number of concrete bit-strings.
In (almost?) all the other texts, Chaitin's Theorem is formulated by assuming the so-called "semantical soundness" of T, i.e. by assuming (somewhat irresponsibly) that T proves only "true" formulas of the language of PA (whatever it means). Then, first, the formula AcEn0An(n>n0 -> K(n)>c) is "obviously, true", and a) can be omitted. Secondly, since T is "obviously, consistent", then b) can be put simply as: T does not prove K(n)>eT for none of n. In this way we obtain almost one of Chaitin's own formulations of his theorem:
Chaitin's Theorem. For any semantically sound fundamental formal theory T one can construct a number eT such that, for all numbers n, T does not prove that K(n)>eT (while this formula is true for all n, except for a finite number of exceptions).
It follows from Chaitin's original proof that we can have: eT = AT+B, where AT is the Kolmogorov complexity of the formulation of theory T (or, of its axioms, if rules of inference are universally fixed), and B - a universal constant, i.e. B does not depend on T.
I.e., in a sense, the possibility of proving the complexity of natural numbers by using some theory T, is limited by the complexity of the formulation of T itself.
In which sense is Chaitin's Theorem stronger than Goedel's Incompleteness Theorem? Try comparing yourself:
Goedel's Theorem says that, for any fundamental formal theory T, there is a Pi1-formula GT such that, if some theory T1 proves the consistency of T, then T1 proves GT, but T does not prove GT.
Chaitin's Theorem says that there is a Pi1-formula C(x) such that PA proves that C(n) is true for infinitely many n-s, but any consistent fundamental formal theory T can prove C(n) only for a finite number of n-s.
Goedel's Theorem is used to make a very general prediction: developing any sufficiently strong mathematical theory, we will run either into contradictions, or into unsolvable problems. And this general prediction was confirmed "experimentally" many times since 1963, when Paul Cohen proved that, if set theory is consistent, then it cannot solve the continuum problem.
As shown in the paper:
Michiel van Lambalgen. Algorithmic information theory. Journal of Symbolic Logic, 1989, 54 (4), pp. 1389 - 1400 (available online)
(see also the above Raatikainen's paper), the phenomenon discovered in Chaitin's Theorem, cannot be used for measuring the "mathematical power" of theories.
One can try to define the "characteristic constant" cT of theory T as follows:
cT = "the least e such that,
for all numbers n, T does not prove K(n)>e"
=
= 1+ "the maximum e such that, for some number n, T
proves K(n)>e".
By Chaitin's Theorem, if T is a consistent fundamental theory, then cT<=eT, i.e. for consistent theories, cT is always some finite number. We know, as a consequence of Goedel's Second Theorem, that set theory ZF is "mathematically more powerful" than first order arithmetic PA. Namely, ZF proves some arithmetical theorems that PA cannot prove (if PA is consistent). But, as noted in Lambalgen's paper: "... we do not know, whether cPA<cZF, and, worse, we even have no idea how to establish results of this sort." (p. 1395).
If we would define the complexity of some assertion as the Kolmogorov complexity of its formulation (i.e. of the corresponding formula), then the complexity of theorems provable in some theory T, will NOT be limited by the complexity of the formulation of T. Indeed, for any limit c, there is only a finite number of formulas having Kolmogorov complexity up to c, but T proves an infinite number of theorems. Hence, the following thesis cannot be true: "... if one has ten pounds of axioms and a twenty-pound theorem, then that theorem cannot be derived from those axioms". But it may become true, if we restrict our assertions to the specific kind of ones used in Chaitin's Theorem, for example, to the assertions of the form K(n)>n. Indeed, while PA proves that K(n)>n is true for infinitely many numbers n, a consistent theory T can prove K(n)>n only for n-s, limited by the complexity of the formulation of T.
Note. More about other attempts to produce incompleteness theorems by modeling various kinds of paradoxes (P.Vopenka 1966, J.L.Krivine 1972, J.Boolos 1989, M.Kikuchi 1994) see:
Cezary Cieslinski. Heterologicality and Incompleteness. Mathematical Logic Quaterly, 2002, vol. 48, N 1, pp. 105-110 (available online at http://www3.interscience.wiley.com/cgi-bin/jissue/85513999).
Back to title page.
universal, formulas, statements, Chaitin, sentences, theorem, consistent, provable, Goldbach conjecture, Berry paradox, Goldbach, conjecture, paradox, Berry, incompleteness, Chaitin theorem