\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}