Gödel’s Incompleteness Theorems and Computer Science

Roman Murawski

Uniwersytet im. Adama Mickiewicza

Wydział Matematyki i Informatyki

ul. Matejki 48/49

60–769 Poznań, Poland

          E-mail: rmur@math.amu.edu.pl

Abstract

In the paper some applications of Gödel’s incompleteness theorems to discussions of problems of computer science are presented. In particular the problem of relations between the mind and machine (arguments by J.J.C. Smart and J.R. Lucas) is discussed. Next Gödel’s opinion on this issue is studied. Finally some interpretations of Gödel’s incompleteness theorems from the point of view of the information theory are presented.

1 Gödel’s theorems and artifical intelligence

Gödel’s incompleteness theorems^{1} have been used as arguments in various discussions of mathematical and metamathematical as well as philosophical problems. Recently they have also appeared in discussions of problems connected with computer science, especially with artificial intelligence.

1Gödel’s incompleteness theorems were proved in his famous paper (1931). They can be found in various handbooks and monographs — see, e.g., Mendelson (1964), Smoryński (1977) or Murawski (199?). Recall that Gödel’s First Incompleteness Theorem states that any consistent

The origins of the latter are connected with A. Turing’s paper “Computing Machinary and Intelligence” (1950). One of the main problems investigated in this domain is the question of whether machines can act in an intelligent way. Note that this problem is in fact very old and was considered already by René Descartes (1596–1650) and Julien Offray de La Mettrie (1709– 1751) who discussed the question of whether a human being is a mechanical machine. Descartes in Discours de la méthode pour bien conduire sa raison et chercher la vérité dans les sciences (1637) answered this question negatively arguing that it is impossible to construct a (mechanical) machine which could perform acts that are characteristic for a human being. On the contrary La Mattrie claimed in L’homme-machine (1748) that thinking is a function of a body and that a human being can be treated as a machine.

The perspective of the eighteenth century thinkers was naturally restricted to mechanical machines. New aspects of the problem appeared with the introduction of symbolical machines (such as Turing machines) and modern computers. It can be now formulated in the form: does the human mind work as a formalized system, can a computer program be treated as a model of the human mind. At the beginning of the sixties two papers appeared in which an attempt was made to answer this question using Gödel’s theorems: Smart (1961) and Lucas (1961). They caused a long and interesting debate.^{2}

recursively enumerable (recursively axiomatizable) first-order theory containing the arithmetic of natural numbers is essentially incomplete. Gödel’s Second Incompleteness Theorem says that no such theory proves its own consistency (here some additional conditions on the formula that expresses the metamathematical notion of consistency must be satisfied).

2The arguments of Lucas were criticized in particular by I.J. Good in (1967) and (1969) and P. Benacerraf in (1967). Lucas defended his position in (1967) and (1968). See also Hofstadter (1979) and Penrose (1989) and (1994).

Smart understands by a machine a Turing machine and is of the opinion that (cf. Smart (1961), p. 105):

Recent tendencies in biology and psychology have made plausible, to some of us at any rate, the view that men are complicated mechanisms.

He uses in his argumentation Gödel’s theorem and writes (pp. 105–106):^{3}

Consider a formal language L_{0} adequate for elementary number theory. Gödel has shown that if elementary number theory is consistent there is some closed arithmetical sentence expressible in the symbolism of L_{0} which can not be proved or disproved in L_{0}. By reasoning which makes use of the syntax language of L_{0}, however, we can show that this proposition which is undecidable within L_{0} is in fact true. Corresponding to any formal language L_{0} (with constructive rules of proof) we can specify some Turing machine (or computer) T_{0} which if given enough time will produce a proof or disproof of any decidable closed arithmetical sentence of L_{0}. The machine will not of course ever produce for us a proof of a Gödelian undecidable proposition of L_{0}, for no such proof exists. A proof does exist in the language L_{1}, which is the language got by adjoining the syntax language of L_{0} to L_{0}. To L_{1} will correspond a machine T_{1}, which if given enough time will produce a proof of the original sentence undecidable in L_{0}. However in L_{1} there will be another proposition undecidable within it but which we by using the syntax language of L_{1} can show to be true. And so on. Consider the sequence of languages L_{0}, L_{1}, L_{2}, … and the sequence of machines T_{0}, T_{1}, T_{2}, … Whatever you like to mention there will always be some proposition which we can prove but it can not.

3Observe that Smart uses here the notion of the syntax language introduced by Carnap; Gödel spoke about metamathematical considerations.

Smart’s argument is now based on the claim that a machine can transform itself into another machine with greater logical power and in this way he comes to the conclusion (p. 106):

If it [the human nervous system — R.M.] is a machine there must be some Turing machine which can do anything it can do.

Let us turn now to Lucas who at the very beginning of his paper (1961) claims that (p. 112):

Gödel’s Theorem seems to me to prove that Mechanism is false, that is, that minds cannot be explained as machines.

His argumentation is as follows.^{4} Lucas wants to show that mathematical abilities of a human being, e.g., his own abilities, are bigger than those of a machine, even if restricted to arithmetical propositions. If Mechanist says that a machine M is equivalent to Lucas, or rather to mathematical powers of Lucas, then Lucas produces the Gödel formula φ_{M} corresponding to the theory T (M) consisting of arithmetical statements provable by M. It is inessential how we define the theory T (M) — the only important thing is that T (M) is semidecidable (i.e., recursively enumerable). It is always the case if one assumes that M is equivalent to a Turing machine (or other standard notion). There are two possibilities now:

Case 1: the theory T (M) is consistent.

Case 2: the theory T (M) is inconsistent.

In the first case the sentence φ_{M} is unprovable by M, i.e., it is unprovable in the theory T (M), but Lucas can prove it by showing that it is true (Lucas uses here Gödel’s theorem together with the assumption that T (M) is consistent). In the second case every sentence is provable by M. But such a provability is useless and Lucas has certainly another notion of provability and consequently is different from the machine M. So in any case Lucas has shown that the machine M cannot be equivalent to him.

4A nice presentation and discussion of Lucas’ argument can be found, e.g., in Krajewski (1993). See also Rucker (1982).

In this way Lucas comes in (1961) to the following conclusion (p. 116):

We are trying to produce a model of the mind which is mechanical — which is essentially “dead” — but the mind, being in fact “alive”, can always go on better than any formal, ossified, dead, system can. Thanks to Gödel’s theorem, the mind always has the last word.

Observe that the above procedure can be mechanized. Let us assume that all machines are listed in a sequence M_{1}, M_{2}, M_{3}, … It is easy to show that there is a recursive function g such that for every n

(∗) if T (M_{n}) is consistent then g(n) is the Gödel number of a (Gödel) sentence which is true and unprovable in T (M_{n}).

An objection to the above argumentation can be made on the basis of (∗). Indeed, if a machine corresponding to the function g can simulate the procedure described above (and called sometimes “out-Gödeling of M”) then machines are not really worse than we are. It can be replied that this machine can be out-Gödeled too. In fact, the aim is not to dominate all machines at once but rather each machine proposed by the Mechanist. Therefore Lucas describes the procedure as dialectical and he writes in (1968, p. 154):

The argument is dialectical. It is an argument between two persons, not a proof sequence constructed by one.

Hence it is a game in which Lucas wins in every move.

Another objection that can be raised is that the procedure does not work if the program of a machine is not known. Hence the mathematical powers of Lucas might be equal to a machine but he would not be able to find an n in order to produce g(n). This leads to the following possibility: perhaps we are a machine but we do not know which one. This can be answered as follows: the appropriate Gödel sentence exists in an objective way and can be used by us at any time. On the other hand if a Mechanist presents a number n then Lucas can produce g(n). The sentence corresponding to it will be true provided the theory T (M_{n}) is consistent.

But here the next problem appears: how do we know that T (M_{n}) is consistent? The set C = {n : T (M_{n}) is consistent} is not recursive,^{5} so the problem “is a given machine consistent” is undecidable. Consequently it is theoretically impossible to distinguish Case 1 and Case 2. To distinguish them requires nonrecursive skills, i.e., the procedure of out-Gödeling assumes a non-mechanical nature of Lucas. But this is the thesis that was supposed to be proved!

In this situation one can argue that either Case 1 or Case 2 holds and hence the whole argument still works. But now the procedure becomes nonconstructive and its dialectical character is doubtful.

Since Gödel sentences for inconsistent theories are false and contradict even the most elementary arithmetical truths, i.e., truths that can be formulated as formulas with bounded quantifiers only,^{6} Lucas is not allowed to commit even a single mistake. Indeed, his argument in Case 2 depends entirely on his consistency and if he presented Gödel sentence as a sentence proving his superiority over machines, he would fall into inconsistency.

5Assume that C is recursive. Then C′ = {g(n) : n ∈ C} is recursively enumerable. Hence C′ = T (M_{k}) for some k. Since all g(n) for n ∈ C are true, it follows that k ∈ C. By the definition g(k) is unprovable in T (M_{k}).

But on the other hand g(k) ∈ T (M_{k}), a contradiction.

6Gödel’s undecidable sentence is of the form ∀xφ(x) where φ(x) is a formula containing only atomic formulas, connectives and bounded quantifiers (denote the class of all such formulas φ by BQ). Recall that if ψ is any formula of the form ∃xφ(x) where ψ ∈ BQ and ψ is true in the standard model of the arithmetic of natural numbers then ψ is provable in Peano arithmetic PA.

So the question if we are consistent turns out to be significant. Lucas in (1961) claims that the answer is negative and writes (p. 120):

… are not men inconsistent too? Certainly women are, and politicians; and even male non-politicians contradict themselves sometimes, and a single inconsistency is enough to make a system inconsistent.

And he adds (p. 123):

… if we find that no system containing simple arithmetic can be free of contradictions, we shall have to abandon not merely the whole of mathematics and the mathematical sciences, but the whole of thought.

The assumption that mathematics (and we ourselves as well!) are consistent is necessary to do mathematics. But it should be noted that it may happen that proofs of contradictions are too long to matter in practice and that it is possible to remain in safe contradiction-free areas all the time.^{7} Gödel’s Second Theorem seems to imply that our consistency cannot be proved in a mathematical, formal way even if we are consistent. In practice we believe that we are in principle consistent or rather that we can correct and remove any inconsistencies when they appear. Lucas puts it in the following way (1961, p. 122):

… the mind does indeed try out dubious axioms and rules of inference; but if they are found to lead to contradiction, they are rejected altogether. We try out axioms and rules of inference provisionally-true: but we do not keep them, once they are found to lead to contradictions.

The belief that we are in principal consistent does not, however, assure that Lucas’ argument is right. Indeed, G. Lee Bowie remarked in (1982) that whatever Lucas may claim about his own consistency, we know enough to prove that he is actually inconsistent. Lucas’ procedure can be expressed as the recursiveness of the function g satisfying the condition (∗) formulated above. But the range of g, i.e., the set

7This is the case with large computer programs. Note also that the infinitesimal calculus was developed for centuries on inconsistent foundations.

A = {the sentence with Gödel number ; g(n) : n ∈ N}

is inconsistent. This can be proved in the following way: Since g is recursive, the set A is recursively enumerable. Hence one can assume that it is generated by a machine M_{k} for some k ∈ N. If A were consistent then by (∗) the sentence with Gödel number g(k) would be unprovable in T (M_{k}). Yet it is an element of A and consequently it belongs to T (M_{k}). This is a contradiction.

It seems impossible to modify Lucas’ argument to avoid the above criticism — cf. Krajewski (1983) and (1993).

Though no convincing arguments in favour of or against the mechanistic thesis were proposed so far, it seems that Gödel’s results support the moderate opinion of Nagel and Newman formulated in (1958, pp. 100-101) in the following way:^{8}

Given a definite problem, a machine … might be built for solving it; but no one such machine can be built for solving every problem. The human brain may, to be sure, have built-in limitations of its own, and there may be mathematical problems it is incapable of solving. But, even so, the brain appears to embody a structure of rules of operation which is far more powerful than the structure of currently conceived artificial machines. There is no immediate prospect of replacing the human mind by robots.

8Though formulated almost forty years ago, when computers and artifical intelligence were at the beginnings of their development, it seems to be still valid.

2 Gödel on the mind–body problem

What was the opinion of Gödel concerning the problem of interrelations between his incompleteness theorems and the question whether our minds can be treated as machines? Note first that Gödel was looking for arguments that “laws of thought are not mechanical” — cf. Kreisel (1980), p. 216. In the 25th Josiah Willard Gibbs Lecture “Some basic theorems on the foundations of mathematics and their implications”^{9} Gödel considered implications of his incompleteness theorems for the problem of relations between mind and machine. One of the implications is that the human mind is incapable of formulating or mechanizing all its mathematical intuitions. Therefore one can speak about certain incompletability of mathematics. Gödel wrote (p. 309):

… it [Second Incompleteness Theorem — R.M.] makes it impossible that someone should set up a certain welldefined system of axioms and rules and consistently make the following assertion about it: All of these axioms and rules I perceive (with mathematical certitude) to be correct, and moreover I believe that they contain all of mathematics. If someone makes such a statement he contradicts himself. For if he perceives the axioms under consideration to be correct, he also perceives (with the same certainty) that they are consistent. Hence he has a mathematical insight not derivable from his axioms.

On the other hand Gödel noted that on the basis of what has been proved so far, it remains possible that (pp. 309–310):

the human mind (in the realm of pure mathematics) is equivalent to a finite machine that, however, is unable to understand completely its own functioning.

9Gödel delivered this lecture at the meeting of the American Mathematical Society at Brown University on 26th December 1951. It was first published in the volume III of his Collected Works — cf. Gödel (1951).

This means that such a machine would be equivalent to mathematical intuition but on the other hand it would be impossible to prove that fact, or even to prove that the machine yields only correct theorems. This possibility follows from Gödel’s Second Theorem under the assumption that our mind is consistent. Gödel treated the latter as granted.

The second important implication is formulated by Gödel in the following way (p. 310):

Either mathematics is incompletable in this sense, that its evident axioms can never be comprised in a finite rule, that is to say, the human mind (even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems … (where the case that both terms of the disjunction are true is not excluded, so that there are, strictly speaking, three alternatives).

Gödel claimed hovever that the history of mathematics forced us to reject the second alternative. His argumentation is summerized by Hao Wang in the following way (1974, pp. 324–325):

If it were true it would mean that human reason is utterly irrational by asking questions it cannot answer, while asserting emphatically that only reason can answer them. Human reason would then be very imperfect and, in some sense, even inconsistent, in glaring contradiction to the fact that those parts of mathematics which have been systematically and completely developed (such as, e.g. the theory of 1st and 2nd degree Diophantine equations, the latter with two unknowns) show an amazing degree of beauty and perfection.

Certain ‘rationalistic optimism’ can be seen here. In this way Gödel shared Hilbert’s belief expressed in (1926) in the words:

In mathematics there is no ignorabimus,

and repeated at the end of his speech over the local radio station in Königsberg in September 1930, just after the conference during which Gödel announced his incompleteness result:

Wir müssen wissen. Wir werden wissen. (We must know. We shall know.)

In Gödel’s opinion the attempted proofs for the equivalence of the mind and machines were fallacious. This follows, e.g., from the following unpublished paragraph about Turing’s alleged proof that every mental procedure for producing an infinite series of integers is equivalent to a mechanical procedure:^{10}

Turing, in Proc. Lond. Math. Soc. 42 (1936), p. 250, gives an argument which is supposed to show that mental procedures cannot carry any further than mechanical procedures. However, this argument is inconclusive, because it depends on the supposition that a finite mind is capable of only a finite number of distinguished states. What Turing disregards completely is the fact that mind, in its use, is not static, but constantly developing. This is seen, e.g., from the infinite series of ever stronger axioms of infinity in set theory, each of which expresses a new idea or insight. A similar process takes place with regard to the primitive terms. E.g., the iterative concept of set became clear only in the past few decades. Several more primitive ideas now appear on the horizon, e.g., the selfreflexive concept of proper class. Therefore, although at each stage of the mind’s development the number of its possible states is finite, there is no reason why this number should not converge to infinity in the course of its development. Now there may exist systematic methods of accelerating, specializing, and uniquely determining this development, e.g., by asking the right questions on the basis of a mechanical procedure. But it must be admitted that the precise definition of a procedure of this kind would require a substantial deepening of our understanding of the basic operations of the mind. Vaguely defined procedures of this kind, however, are known, e.g., the process of defining recursive wellorderings of integers representing larger and larger ordinals or the process of forming stronger and stronger axioms of infinity in set theory.

10This paragraph was to be added as a footnote at the word ‘mathematics’ on p. 73, line 3 of the English translation of Gödel (1931) in Davis (1965).

It is quoted here according to Wang Hao (1974), pp. 326–327.

In discussions with Hao Wang (cf. Wang Hao (1974), p. 326) Gödel added that Turing’s argument became valid under two additional assumptions: (1) there is no mind separated from matter, and (2) the brain functions basically like a digital computer (or (2’) the physical laws, in their observable consequences, have a finite limit of precision). Gödel treated (2) as very likely and (2’) as practically certain. On the other hand he believed that (1) was (cf. Wang Hao (1974), p. 326):

a prejudice of our time, which will be disproved scientifically (perhaps by the fact that there aren’t enough nerve cells to perform the observable operations of the mind).

3 Information theory and Gödel’s incompleteness theorems

Gödel’s theorems were investigated and interpreted also from the point of view of the information theory. We cannot present here the appropriate technical considerations (they can be found, e.g., in Chaitin (1974) and (1982)). Information theory suggests that the phenomenon revealed by Gödel’s incompleteness theorems is natural and widespread, not pathological and unusual. The results obtained in it lead to the following corollaries: if a certain effective (recursive) set of methods of reasoning has been precized ahead then there is an upper bound to the complexity of theorems that can be proved in such a system. Consequently, if one wishes to obtain more complex theorems (in the sense of the information theory, i.e., theorems containg more information) then one will have to continually introduce new axioms and new methods. Neither the admissible methods and rules can be fixed and codified nor the concept of a correct mathematical proof can be defined once and for ever. Hence, progress in mathematics seems to be much like progress in the natural sciences than hitherto expected. Note that such a thesis was already stated by Gödel in (1944) where he wrote on pp. 127–128:

The analogy between mathematics and a natural science is enlarged upon by Russell also in another respect … axioms need not be evident in themselves, but rather their justification lies (exactly as in physics) in the fact that they make it possible for these “sense perceptions” to be deduced … I think that … this view has been largely justified by subsequent developments, and it is to be expected that it will be still more so in the future. It has turned out that solution of certain arithmetical problems requires the use of assumptions essentially transcending arithmetic … Furthermore it seems likely that for deciding certain questions of abstract set theory and even for certain related questions of the theory of real numbers new axioms based on some hitherto unknown idea will be necessary. Perhaps also the apparently unsurmountable difficulties which some other mathematical problems have been presenting for many years are due to the fact that the necessary axioms have not yet been found. Of course, under these circumstances mathematics may lose a good deal of its “absolute certainty”; but, under the influence of the modern criticism of the foundations, this has already happened to a large extent.

All such arguments are used by quasi-empiricism (cf., e.g., Putnam (1975)) which claims that mathematical knowledge is not a priori, absolute and certain but it is rather quasi-empirical, fallible and probable, it is in fact much like natural sciences.

References

Benacerraf P. (1967), God, the Devil, and Gödel, The Monist 51,

9–32. Bowie G.L. (1982), Lucas’ Number Is Finally Up, Journal of Philo-

sophical Logic 11, 279–285. Chaitin G. (1974), Information-Theoretic Computational Complex-

ity, IEEE Transactions on Information Theory IT-20, 10–15. Reprinted in: Tymoczko Th. (Ed.), New Directions in the Philosophy of Mathematics. An Anthology, Boston-Basel-Stuttgart 1985, Birkhäuser, pp. 289–299.

Chaitin G. (1982), Gödel’s Theorem and Information, International Journal of Theoretical Physics 21, 941–954. Reprinted in: Tymoczko Th. (Ed.), New Directions in the Philosophy of Mathematics. An Anthology, Boston-Basel-Stuttgart 1985, Birkhäuser, pp. 300–311.

Davis M. (Ed.) (1965), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Hewlett, N.Y., Raven Press.

Descartes R. (1637), Discours de la méthode pour bien conduire sa raison et chercher la vérité dans les sciences. Reprinted in: Oeuvres complètes, Adam Ch. and Tannery P. (Eds.), Paris 1897–1913, second edition: Paris 1956–1957.

Gödel K. (1931), Über formal unentscheidbare Sätze der ‘Principia Mathematica’ und verwandter Systeme. I, Monatshefte für Mathematik und Physik 38, 173–198. Reprinted with English translation: On Formally Undecidable Propositions of Principia Mathematica and Related Systems, in: Gödel K., Collected Works, vol. I, ed. by Feferman S. et al., Oxford University Press, New York and Clarendon Press, Oxford, 1986, pp. 144–195.

Gödel K. (1944), Russell’s Mathematical Logic. In: Schilpp P.A. (Ed.), The Philosophy of Bertrand Russell, Evanston, Northwestern University, pp. 123–153. Reprinted in: Gödel K., Collected Works, vol. II, ed. by Feferman S. et al., New York and Oxford, 1990, Oxford University Press, pp. 119–141.

Gödel K. (1951), Some Basic Theorems on the Foundations of Mathematics and Their Implications, first published in: Gödel K., Collected Works, vol. III, ed. by Feferman S. et al., New York and Oxford 1995, Oxford University Press, pp. 304–323.

Good I.J. (1967), Human and Machine Logic, British Journal for the

Philosophy of Science 18, 145–146. Good I.J. (1969), Gödel’s Theorem is a Red Herring, British Journal

for the Philosophy of Science 19, 357–358. Hilbert D. (1926), Über das Unendliche, Mathematische Annalen 95,

161–190; English translation: On the Infinite, in: Heijenoort J. van (Ed.), From Frege to Gödel. A Source Book in Mathematical Logic, 1879–1931 , Cambridge, Mass., 1967, Harvard University Press, pp. 367–392.

Hofstadter D.R. (1979), Gödel, Escher, Bach: An Eternal Golden

Briad, New York, Basic Books. Krajewski S. (1983), Philosophical Consequences of Gödel’s Theo-

rems, Bulletin of the Section of Logic 12, 157–164. Krajewski S. (1993), Did Gödel Prove That we Are Not Machines?.

In: Wolkowski Z.W. (Ed.), First International Symposium on Gödel’s Theorems, Singapore-New Jersey-London-Hong Kong, World Scientific, pp. 39–49.

Kreisel G. (1980), Kurt Gödel 1906–1978, Biographical Memoires of

Fellows of the Royal Society 26, 149–224. La Mettrie J.O. de (1748), L’homme-machine. Critical edition, A.

Vartanian (Ed.), Paris 1960. Lucas J.R. (1961), Minds, Machines and Gödel, Philosophy 36, 112–

127. Reprinted in: Anderson A.R. (Ed.), Minds and Machines, Prentice Hall, Englewood Cliffs 1964.

Lucas J.R. (1967), Human and Machine Logic. A Rejoinder, British

Journal for the Philosophy of Science 19, 155–156. Lucas J.R. (1968), Satan Stultified: A Rejoinder to Paul Benacerraf,

The Monist 52, 145–158. Mendelson E. (1964), Introduction to Mathematical Logic, Princeton-

Toronto-New York-London, D. Van Nostrand Company, Inc. Murawski R. (199?), Recursive Functions and Metamathematics, to

appear.

Nagel E. and Newman J.R. (1958), Gödel’s Proof , London, Routledge

& Kegan Paul, Ltd. Penrose R. (1989), The Emperor’s New Mind. Concerning Comput-

ers, Minds, and the Laws of Physics, Oxford, Oxford University Press.

Penrose R. (1994), Shadows of the Mind: a Search for the Missing Science of Consciousness, Oxford-New York-Melbourne, Oxford University Press.

Putnam H. (1975), What Is Mathematical Truth?. In: H. Putnam, Mathematics, Matter and Method. Philosophical Papers, vol. I, Cambridge-London-New York-Melbourne, Cambridge University Press, pp. 60–78. Reprinted in: Tymoczko Th. (Ed.), New Directions in the Philosophy of Mathematics. An Anthology, Boston-Basel-Stuttgart 1985, Birkhäuser, pp. 50–65.

Rucker R. (1982), Infinity and the Mind, Boston-Basel-Stuttgart,

Birkhäuser. Smart J.J.C. (1961), Gödel’s Theorem, Church’s Thesis, and Mecha-

nism, Synthese 13, 105–110. Smoryński C. (1977), The Incompleteness Theorems. In: Barwise

J. (Ed.), Handbook of Mathematical Logic, Amsterdam, North-Holland Publ. Comp., pp. 821–865.

Turing A. (1950), Computing Machinery and Intelligence, Mind 59, 433–460. Reprinted in: Anderson A.R. (Ed.), Minds and Machines, Prentice Hall, Englewood Cliffs 1964, pp. 4–42.

Wang Hao (1974), From Mathematics to Philosophy, London, Routledge and Kegan Paul.