\documentstyle[12pt]{article} \oddsidemargin 12mm \evensidemargin 12mm \topmargin 10mm \textheight 185mm \textwidth 115mm \newcommand{\N}{{\Bbb N}} \newcommand{\rec}{recursive} \newcommand{\undec}{undecidable} \newcommand{\m}{mathematics} %\input amssym12.def %\input amssym \title{G\"odel's Incompleteness Theorems\\ and Computer Science} \begin{document} \author{Roman Murawski\\ {\small Uniwersytet im. Adama Mickiewicza}\\ {\small Wydzia\l\ Matematyki i Informatyki}\\ {\small ul. Matejki 48/49}\\ {\small 60--769 Pozna\'n, Poland}\\ {\small E-mail: {\tt rmur@math.amu.edu.pl}}} \date{} \maketitle \begin{abstract} In the paper some applications of G\"odel'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\"odel's opinion on this issue is studied. Finally some interpretations of G\"odel's incompleteness theorems from the point of view of the information theory are presented. \end{abstract} \section{G\"odel's theorems and artifical intelligence} G\"odel's incompleteness theorems\footnote{G\"odel'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\'nski (1977) or Murawski (199?). Recall that G\"odel's First Incompleteness Theorem states that any consistent recursively enumerable (recursively axiomatizable) first-order theory containing the arithmetic of natural numbers is essentially incomplete. G\"odel'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).} 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. 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\'e 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 {\it Discours de la m\'ethode pour bien conduire sa raison et chercher la v\'erit\'e 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 {\it 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\"odel's theorems: Smart (1961) and Lucas (1961). They caused a long and interesting debate.\footnote{The 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): \begin{quote} {\small Recent tendencies in biology and psychology have made plausible, to some of us at any rate, the view that men are complicated mechanisms. } \end{quote} He uses in his argumentation G\"odel's theorem and writes (pp. 105--106):\footnote{Observe that Smart uses here the notion of the syntax language introduced by Carnap; G\"odel spoke about metamathematical considerations.} \begin{quote} {\small Consider a formal language ${\rm L}_{0}$ adequate for elementary number theory. G\"odel has shown that if elementary number theory is consistent there is some closed arithmetical sentence expressible in the symbolism of ${\rm L}_{0}$ which can not be proved or disproved in ${\rm L}_{0}$. By reasoning which makes use of the syntax language of ${\rm L}_{0}$, however, we can show that this proposition which is undecidable within ${\rm L}_{0}$ is in fact true. Corresponding to any formal language ${\rm L}_{0}$ (with constructive rules of proof) we can specify some Turing machine (or computer) ${\rm T}_{0}$ which if given enough time will produce a proof or disproof of any decidable closed arithmetical sentence of ${\rm L}_{0}$. The machine will not of course ever produce for us a proof of a G\"odelian \undec\ proposition of ${\rm L}_{0}$, for no such proof exists. A proof does exist in the language ${\rm L}_{1}$, which is the language got by adjoining the syntax language of ${\rm L}_{0}$ to ${\rm L}_{0}$. To ${\rm L}_{1}$ will correspond a machine ${\rm T}_{1}$, which if given enough time will produce a proof of the original sentence \undec\ in ${\rm L}_{0}$. However in ${\rm L}_{1}$ there will be another proposition \undec\ within it but which we by using the syntax language of ${\rm L}_{1}$ can show to be true. And so on. Consider the sequence of languages ${\rm L}_{0}$, ${\rm L}_{1}$, ${\rm L}_{2}$, \ldots\ and the sequence of machines ${\rm T}_{0}$, ${\rm T}_{1}$, ${\rm T}_{2}$, \ldots\ Whatever you like to mention there will always be some proposition which we can prove but it can not. } \end{quote} 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): \begin{quote} {\small If it [the human nervous system --- R.M.] is a machine there must be some Turing machine which can do anything it can do. } \end{quote} Let us turn now to Lucas who at the very beginning of his paper (1961) claims that (p. 112): \begin{quote} {\small G\"odel's Theorem seems to me to prove that Mechanism is false, that is, that minds cannot be explained as machines. } \end{quote} His argumentation is as follows.\footnote{A nice presentation and discussion of Lucas' argument can be found, e.g., in Krajewski (1993). See also Rucker (1982).} 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\"odel formula $\varphi_{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: \vspace{0.5em} {\it Case 1:\/} the theory $T(M)$ is consistent. \vspace{0.3em} {\it Case 2:\/} the theory $T(M)$ is inconsistent. \vspace{0.5em} \noindent In the first case the sentence $\varphi_{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\"odel'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. In this way Lucas comes in (1961) to the following conclusion (p. 116): \begin{quote} {\small 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\"odel's theorem, the mind always has the last word. } \end{quote} 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}$, \ldots\ It is easy to show that there is a \rec\ function $g$ such that for every $n$ \begin{itemize} \item[$(\ast)$] if $T(M_{n})$ is consistent then $g(n)$ is the G\"odel number of a (G\"odel) sentence which is true and unprovable in $T(M_{n})$. \end{itemize} An objection to the above argumentation can be made on the basis of $(\ast)$. Indeed, if a machine corresponding to the function $g$ can simulate the procedure described above (and called sometimes out-G\"odeling of $M$'') then machines are not really worse than we are. It can be replied that this machine can be out-G\"odeled 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): \begin{quote} {\small The argument is dialectical. It is an argument between two persons, not a proof sequence constructed by one. } \end{quote} 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\"odel 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}) \; \mbox{is consistent} \}$ is not \rec,\footnote{Assume that $C$ is \rec. Then $C' = \{ g(n): n \in C\}$ is recursively enumerable. Hence $C' = T(M_{k})$ for some $k$. Since all $g(n)$ for $n \in C$ are true, it follows that $k \in C$. By the definition $g(k)$ is unprovable in $T(M_{k})$. But on the other hand $g(k) \in T(M_{k})$, a contradiction.} so the problem is a given machine consistent'' is \undec. 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\"odeling 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\"odel 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,\footnote{G\"odel's undecidable sentence is of the form $\forall x \varphi (x)$ where $\varphi(x)$ is a formula containing only atomic formulas, connectives and bounded quantifiers (denote the class of all such formulas $\varphi$ by BQ). Recall that if $\psi$ is any formula of the form $\exists x \varphi(x)$ where $\psi \in {\rm BQ}$ and $\psi$ is true in the standard model of the arithmetic of natural numbers then $\psi$ is provable in Peano arithmetic PA.} 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\"odel sentence as a sentence proving his superiority over machines, he would fall into inconsistency. 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): \begin{quote} {\small \ldots\ 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. } \end{quote} And he adds (p. 123): \begin{quote} {\small \ldots\ 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. } \end{quote} The assumption that \m\ (and we ourselves as well!) are consistent is necessary to do \m. 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.\footnote{This is the case with large computer programs. Note also that the infinitesimal calculus was developed for centuries on inconsistent foundations.} G\"odel'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): \begin{quote} {\small \ldots\ 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. } \end{quote} 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 $(\ast)$ formulated above. But the range of $g$, i.e., the set $$A = \{ \mbox{the sentence with G\"odel number} \ ; g(n): n \in \ N \}$$ is inconsistent. This can be proved in the following way: Since $g$ is \rec, the set $A$ is recursively enumerable. Hence one can assume that it is generated by a machine $M_{k}$ for some $k \in \ N$. If $A$ were consistent then by $(\ast)$ the sentence with G\"odel 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). \vspace{1em} Though no convincing arguments in favour of or against the mechanistic thesis were proposed so far, it seems that G\"odel's results support the moderate opinion of Nagel and Newman formulated in (1958, pp. 100-101) in the following way:\footnote{Though formulated almost forty years ago, when computers and artifical intelligence were at the beginnings of their development, it seems to be still valid.} \begin{quote} {\small Given a definite problem, a machine \ldots\ 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. } \end{quote} \section{G\"odel on the mind--body problem} What was the opinion of G\"odel concerning the problem of interrelations between his incompleteness theorems and the question whether our minds can be treated as machines? Note first that G\"odel 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 \m\ and their implications''\footnote{G\"odel 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 {\it Collected Works\/} --- cf. G\"odel (1951).} G\"odel 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 \m. G\"odel wrote (p. 309): \begin{quote} {\small \ldots\ {\it it\/} [Second Incompleteness Theorem --- R.M.] {\it makes it impossible that someone should set up a certain well-defined system of axioms and rules and consistently make the following assertion about it: All of these axioms and rules I perceive\/} ({\it with mathematical certitude\/}) {\it to be correct, and moreover I believe that they contain all of \m.\/} 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. } \end{quote} On the other hand G\"odel noted that on the basis of what has been proved so far, it remains possible that (pp. 309--310): \begin{quote} {\small the human mind (in the realm of pure \m) {\it is\/} equivalent to a finite machine that, however, is unable to understand completely its own functioning. } \end{quote} 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\"odel's Second Theorem under the assumption that our mind is consistent. G\"odel treated the latter as granted. The second important implication is formulated by G\"odel in the following way (p. 310): \begin{quote} {\small {\it Either \m\ is incompletable in this sense, that its evident axioms can never be comprised in a finite rule, that is to say, the human mind\/} ({\it even within the realm of pure \m}) {\it infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems \ldots} (where the case that both terms of the disjunction are true is not excluded, so that there are, strictly speaking, three alternatives). } \end{quote} G\"odel claimed hovever that the history of \m\ forced us to reject the second alternative. His argumentation is summerized by Hao Wang in the following way (1974, pp.~324--325): \begin{quote} {\small 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 \m\ 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. } \end{quote} Certain rationalistic optimism' can be seen here. In this way G\"odel shared Hilbert's belief expressed in (1926) in the words: \begin{quote} \begin{center} {\small In mathematics there is no {\it ignorabimus\/}, } \end{center} \end{quote} and repeated at the end of his speech over the local radio station in K\"onigsberg in September 1930, just after the conference during which G\"odel announced his incompleteness result: \begin{quote} \begin{center} {\small Wir m\"ussen wissen. Wir werden wissen.\\ (We must know. We shall know.) } \end{center} \end{quote} In G\"odel'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:\footnote{This paragraph was to be added as a footnote at the word mathematics' on p. 73, line 3 of the English translation of G\"odel (1931) in Davis (1965). It is quoted here according to Wang Hao (1974), pp.~326--327.} \begin{quote} {\small Turing, in {\it 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 {\it mind\/}, {\it in its use\/}, {\it is not static\/}, {\it 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 \rec\ wellorderings of integers representing larger and larger ordinals or the process of forming stronger and stronger axioms of infinity in set theory. } \end{quote} In discussions with Hao Wang (cf. Wang Hao (1974), p. 326) G\"odel 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\"odel 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): \begin{quote} {\small 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). } \end{quote} \section{Information theory and G\"odel's incompleteness theorems} G\"odel'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\"odel'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 (\rec) 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 \m\ seems to be much like progress in the natural sciences than hitherto expected. Note that such a thesis was already stated by G\"odel in (1944) where he wrote on pp.~127--128: \begin{quote} {\small The analogy between \m\ and a natural science is enlarged upon by Russell also in another respect \ldots\ 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 \ldots\ I think that \ldots\ 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 \ldots\ 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 \m\ 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. } \end{quote} All such arguments are used by quasi-empiricism (cf., e.g., Putnam (1975)) which claims that mathematical knowledge is not {\it a priori\/}, absolute and certain but it is rather quasi-empirical, fallible and probable, it is in fact much like natural sciences. \section*{References} {\small \hang{\noindent Benacerraf P. (1967), God, the Devil, and G\"odel, {\it The Monist\/} {\bf 51}, 9--32.} \vspace{0.3em} \hang{\noindent Bowie G.L. (1982), Lucas' Number Is Finally Up, {\it Journal of Philosophical Logic\/} {\bf 11}, 279--285.} \vspace{0.3em} \hang{\noindent Chaitin G. (1974), Information-Theoretic Computational Complexity, {\it IEEE Transactions on Information Theory\/} {\bf IT-20}, 10--15. Reprinted in: Tymoczko Th. (Ed.), {\it New Directions in the Philosophy of Mathematics. An Anthology\/}, Boston-Basel-Stuttgart 1985, Birkh\"auser, pp. 289--299. } \vspace{0.3em} \hang{\noindent Chaitin G. (1982), G\"odel's Theorem and Information, {\it International Journal of Theoretical Physics\/} {\bf 21}, 941--954. Reprinted in: Tymoczko Th. (Ed.), {\it New Directions in the Philosophy of Mathematics. An Anthology\/}, Boston-Basel-Stuttgart 1985, Birkh\"auser, pp. 300--311. } \vspace{0.3em} \hang{\noindent Davis M. (Ed.) (1965), {\it The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions\/}, Hewlett, N.Y., Raven Press.} \vspace{0.3em} \hang{\noindent Descartes R. (1637), {\it Discours de la m\'ethode pour bien conduire sa raison et chercher la v\'erit\'e dans les sciences\/}. Reprinted in: {\it Oeuvres compl\etes\/}, Adam Ch. and Tannery P. (Eds.), Paris 1897--1913, second edition: Paris 1956--1957. } \vspace{0.3em} \hang{\noindent G\"odel K. (1931), \"Uber formal unentscheidbare S\"atze der Principia Mathematica' und verwandter Systeme. I, {\it Monatshefte f\"ur Mathematik und Physik\/} {\bf 38}, 173--198. Reprinted with English translation: On Formally Undecidable Propositions of Principia Mathematica and Related Systems, in: G\"odel K., {\it Collected Works\/}, vol. I, ed. by Feferman~S. {\it et al.}, Oxford University Press, New York and Clarendon Press, Oxford, 1986, pp. 144--195. } \vspace{0.3em} \hang{\noindent G\"odel K. (1944), Russell's Mathematical Logic. In: Schilpp P.A. (Ed.), {\it The Philosophy of Bertrand Russell}, Evanston, Northwestern University, pp. 123--153. Reprinted in: G\"odel K., {\it Collected Works\/}, vol. II, ed. by Feferman~S. {\it et al.}, New York and Oxford, 1990, Oxford University Press, pp. 119--141. } \vspace{0.3em} \hang{\noindent G\"odel K. (1951), Some Basic Theorems on the Foundations of Mathematics and Their Implications, first published in: G\"odel K., {\it Collected Works\/}, vol. III, ed. by Feferman~S. {\it et al.}, New York and Oxford 1995, Oxford University Press, pp. 304--323.} \vspace{0.3em} \hang{\noindent Good I.J. (1967), Human and Machine Logic, {\it British Journal for the Philosophy of Science\/} {\bf 18}, 145--146.} \vspace{0.3em} \hang{\noindent Good I.J. (1969), G\"odel's Theorem is a Red Herring, {\it British Journal for the Philosophy of Science\/} {\bf 19}, 357--358.} \vspace{0.3em} \hang{\noindent Hilbert D. (1926), \"Uber das Unendliche, {\it Mathematische Annalen\/} {\bf 95}, 161--190; English translation: On the Infinite, in: Heijenoort J. van (Ed.), {\it From Frege to G\"odel. A Source Book in Mathematical Logic, 1879--1931\/}, Cambridge, Mass., 1967, Harvard University Press, pp. 367--392. } \vspace{0.3em} \hang{\noindent Hofstadter D.R. (1979), {\it G\"odel, Escher, Bach: An Eternal Golden Briad\/}, New York, Basic Books. } \vspace{0.3em} \hang{\noindent Krajewski S. (1983), Philosophical Consequences of G\"odel's Theorems, {\it Bulletin of the Section of Logic\/} {\bf 12}, 157--164.} \vspace{0.3em} \hang{\noindent Krajewski S. (1993), Did G\"odel Prove That we Are Not Machines?. In: Wolkowski Z.W. (Ed.), {\it First International Symposium on G\"odel's Theorems\/}, Singapore-New Jersey-Lon\-don-Hong Kong, \linebreak World Scientific, pp. 39--49. } \vspace{0.3em} \hang{\noindent Kreisel G. (1980), Kurt G\"odel 1906--1978, {\it Biographical Memoires of Fellows of the Royal Society\/} {\bf 26}, 149--224.} \vspace{0.3em} \hang{\noindent La Mettrie J.O. de (1748), {\it L'homme-machine\/}. Critical edition, A. Var\-ta\-nian (Ed.), Paris 1960. } \vspace{0.3em} \hang{\noindent Lucas J.R. (1961), Minds, Machines and G\"odel, {\it Philosophy\/} {\bf 36}, 112--127. Reprinted in: Anderson A.R. (Ed.), {\it Minds and Machines\/}, Prentice Hall, Englewood Cliffs 1964. } \vspace{0.3em} \hang{\noindent Lucas J.R. (1967), Human and Machine Logic. A Rejoinder, {\it British Journal for the Philosophy of Science\/} {\bf 19}, 155--156.} \vspace{0.3em} \hang{\noindent Lucas J.R. (1968), Satan Stultified: A Rejoinder to Paul Benacerraf, {\it The Monist\/} {\bf 52}, 145--158.} \vspace{0.3em} \hang{\noindent Mendelson E. (1964), {\it Introduction to Mathematical Logic\/}, Princeton-Toronto-New York-London, D. Van Nostrand Company, Inc. } \vspace{0.3em} \hang{\noindent Murawski R. (199?), {\it Recursive Functions and Metamathematics}, to appear. } \vspace{0.3em} \hang{\noindent Nagel E. and Newman J.R. (1958), {\it G\"odel's Proof\/}, London, Routledge \& Kegan Paul, Ltd.} \vspace{0.3em} \hang{\noindent Penrose R. (1989), {\it The Emperor's New Mind. Concerning Computers, Minds, and the Laws of Physics\/}, Oxford, Oxford University Press.} \vspace{0.3em} \hang{\noindent Penrose R. (1994), {\it Shadows of the Mind: a Search for the Missing Science of Consciousness\/}, Oxford-New York-Melbourne, Oxford University Press.} \vspace{0.3em} \hang{\noindent Putnam H. (1975), What Is Mathematical Truth?. In: H.~Putnam, {\it Mathematics, Matter and Method. Philosophical Papers\/}, vol. I, Cambridge-London-New York-Melbourne, Cambridge University Press, pp. 60--78. Reprinted in: Tymoczko Th. (Ed.), {\it New Directions in the Philosophy of Mathematics. An Anthology\/}, Boston-Basel-Stuttgart 1985, Birkh\"auser, pp. 50--65.} \vspace{0.3em} \hang{\noindent Rucker R. (1982), {\it Infinity and the Mind\/}, Boston-Basel-Stuttgart, Birkh\"auser.} \vspace{0.3em} \hang{\noindent Smart J.J.C. (1961), G\"odel's Theorem, Church's Thesis, and Mechanism, {\it Synthese\/} {\bf 13}, 105--110.} \vspace{0.3em} \hang{\noindent Smory\'nski C. (1977), The Incompleteness Theorems. In: Barwise J. (Ed.), {\it Handbook of Mathematical Logic\/}, Amsterdam, North-Holland Publ. Comp., pp. 821--865.} \vspace{0.3em} \hang{\noindent Turing A. (1950), Computing Machinery and Intelligence, {\it Mind\/} {\bf 59}, 433--460. Reprinted in: Anderson A.R. (Ed.), {\it Minds and Machines\/}, Prentice Hall, Englewood Cliffs 1964, pp. 4--42.} \vspace{0.3em} \hang{\noindent Wang Hao (1974), {\it From Mathematics to Philosophy}, London, Routledge and Kegan Paul.} } \end{document} 