Witold Marciszewski
Chair of Logic, Informatics and Philosophy of Science (Head)
University of Bialystok, Poland
e-mail: witmar@calculemus.org
http://www.calculemus.org/
==============================================================
\documentstyle[11pt]{article}
\pagestyle{plain}
\begin{document}
\title{The Two Origins of Modern Logic 1879, 1936}
\author{Witold Marciszewski\thanks
{The research which resulted in this paper was supported by the Polish State
Committee for Science (Komitet Bada\'n Naukowych), Section for Automatics,
Electronics, Computer Science and Telecommunication, grant no.\ 8T11C01812
concerned with {\it the role of the theory of automated reasoning for
comparing natural and artificial intelligence.}} \date{{}}}
\maketitle
\tableofcontents
\bigskip\noindent
Periodization of a historical process imposes a structure and
order upon the flux of events. The structure results both from causal
relations and from assigning values to events; the greater value is
attached to an event, the more it counts in the given structure. This
essay distinguishes two events of utmost significance, being turning
points in the development of modern logic, each of them originating a new
phase.
At the beginning of modern logic there are the works of Frege, Russell,
Peano and Peirce, to which the way was paved by Boole and precursed by
Leibniz. The choice of 1879, the date of publishing Frege's {\it
Begriffsschrift,} is motivated by its chronological antecedency as well as
its author's deep awareness of the nature of modern logic, the latter
expressed in the subtitle to run as follows: {\it eine der
arithmetischen nachgebildete Formelsprache des reinen Denkens} --- a
symbolic language of pure thought, modeled upon that of arithmetic.%
\footnote{The translation of the subtitle follows that of [van Heijenoort
1967] except for the term `Formelsprache' which is there literally
translated into `a formula langauge'. The term `symbolic language' is
preferred here as being commonly accepted and, at the same time, true to
Frege's intentions as his referring to Leibniz's universal
characteristic.}
This phrase defines the first origin of modern logic, and hints at its
bearing on the discoveries of 1931-1936 which so deeply reformed logic
that they can be seen as its new origin. Another reason of the
periodization proposed amounts to the impact of the second origin on the
current research in Artificial Intelligence or, more generally, on
intelligence research. intelligence.%
\footnote{The phrase ``intelligence research'' is to comprise the issues
of both natural and artificial intelligence in their mutual relations, as
noticed in the textbook [Winston 1984, p.\ 3]: ``knowledge about
human information processing can help make computers intelligent'' and,
vice versa, ``the methodology involved in making smart programs may
transfer to making smart people''.}
The first AI project, due to [Turing 1948] and then [Turing 1950], is
based on Turing's momentous study of 1936. His notion of computability
makes it possible to draw a line between algorithmic (mechanical) and
creative processes; hence the import of this notion for intelligence
research.
From the AI perspective, the period that yields the foundations for the
inteligence research should be defined as one between 1931 (G\"odel's
discovery of the incompleteness of arithmetic) and 1943. The latter is the
date of McCulloch's and Pitts' paper ``A logical calculus of ideas
immanent in nervous activity''. Turing's work of 1936 --- forming a link
between G\"odel and the logic of neural networks --- is found,
approximately, in the middle of that interval. Hence the date 1936 can
function as ``pars pro toto'' to symbolize the significance of
the whole period.
\section %%1
{The first origin and `Universal Characteristic'}
\subsection %%1.1 ----------------------------
{Merits and demerits of Aristotele's logic}
The rise of logic, even in the restricted form existing before Frege,
required two ideas: (i) that there are linguistic structures which can be
transformed into other linguistic structures, and (ii) that some
expressions are truth-bearers whose transformations, i.e. structural
changes, are truth-preserving. These insights, even if not stated in an
explicit way, lie at the bottom of Aristotelian logic. A sequence of
truth-preserving transformations amounts to a {\it proof}; it starts from
what one already knows (premises), and ends at what one wishes to know
(conclusion).
When Aristotle was building his theory of proof, the practice of proving
was exercised by mathematicians, as seen in the work of Euclid. Their idea
of proof might have been like Aristotle's, but the linguistic structures
in their demonstrations hardly coincided with those of Aristotle's
syllogistic. The mathematicians deal with individual (though abstract)
objects, which are banned from syllogistic, and they frequently use
relational (i.e., many-place) predicates, while Aristotle admitted
one-place predicates alone; thus there is no place with him for inferences
like ``$y$ lies between $x$ and $z$, hence $y$ lies between $z$ and $x$''.
The main merit of the Aristotelian approach consists in its closeness to
natural languages, as Greek, Latin, etc. That is, in the lack of variables
and in the related feature of using general names (instead of individual
terms combined with predicates, as in mathematical formulas).
Its handicap consists in its being unable to deal with
individuals and relations, while proper names and relational predicates
constantly appear in natural languages.%
\footnote{Interestingly enough, the schoolmen were not able to
syllogistically express their arguments for God's (an individual's!)
existence, since a typical premiss in such arguments takes the following
relational form: ``for any $x$ there is $y$ such that $R(y,x)$''.}
\subsection %%1.2. -------------------------
{Begriffsschrift compared with the Leibnizian project}
This essay is to show how the discoveries of 1936 provided something like
a counterpoint to Frege's vision of logic which in an important respect
was similar to Leibniz's vision. The contrast between Frege's approach and
that after G\"odel should justify the phrase `two origins'. With the first
origin, there dominated the belief that whatever could be grasped and
decided by the pure thought could be truly rendered in a properly devised
symbolic language. The second origin consisted in realizing the opposite:
that syntactic, i.e., algorithmic, means, as characteristic of symbolic
language, not always succeed in making a question, expressed in that
symbolism, a decidable problem (even if the problem is successfully
handled by ``thought in itself'').
Let us list, following a passage in [van Heijenoort 1967, p.\ 1],
the main points of what has been offered by {\it Begriffsschrift}.
\begin{quote}
``Its fundamental contributions are the truth-functional propositional
calculus, the analysis of the proposition into function and argument(s)
instead of subject and predicate, the theory of quantification, a system
of logic in which derivations are carried out exclusively according to the
form of expressions, and a logical definition of the notion of
mathematical sequence.''
\end{quote}
Let it be added that Frege's system of logic has been axiomatized, for the
first time in the history of logic, and that the Fregean method of
quantification takes into account many-place (relational) predicates;
hence no longer the inference as ``$y$ is between $x$ and $z$, hence $y$
is between $z$ and $x$'' will make any difficulties.
There is a patent Leibnizian legacy in Frege's project. In the Preface
to {\it Begriffsschrift} he declares his intention of accomplishing
Leibniz's {\it universal characteristic}, though being at the same time
aware that its full realization is not likely. However, he believed that
the problem of creating a universal characteristic may be conquered by a
gradual advance, and hoped that his work would esentially contribute to
such a progress.
Frege was aware of another difference between him and Leibniz:
that, unlike Leibniz, he does not start from concepts in order to build up
thoughts or propositions out of them; ``instead -- he continues -- I
obtain the components of a thought by decomposition of the thought. In
this respect my Begriffschrift differs from similar creations of Leibniz
and his successors.''%
\footnote
{Quoted after footnote {\it b} in [van Heijenoort 1967, p.\ 1]. The
unpublished fragment in question is dated 26 July 1919.}
However, these were minor differences when compared with similarity of the
main features. Frege confirms the Leibnizian provenience of his project,
answering a comment by Ernst Schr\"oder who objected that Frege did not do
justice to Boole's previous achievements. The reply [Frege 1883] is to the
effect that the goal which was set up in {\it Begriffschrift} is
essentially more extensive than that of Boole. In explaining the
difference, he refers to Leibniz's notions of calculus ratiocinator, a
calculus for reasoning, and lingua characteristica: the former is
involved in the latter, thus Frege's project is more thoroughgoing than
Boole's.%
\footnote
{The original text runs as follows. ``Bei [Schr\"oders] Vorwurfe ist aber
dies haupts\"achlich ubersehen, dass mein Zweck ein anderer als Booles
war. Ich wollte nicht eine abstracte Logik in Formeln darstellen, sondern
einen Inhalt durch geschriebene Zeichen in genauerer und \"ubersichtlicher
Weise zum Ausdruck bringen, als es durch Worte m\"oglich ist. Ich wollte
in der That nicht einen blossen ``calculus ratiocinator", sondern eine
``lingua characteristica" im leibnizischen Sinne schaffen, wobei ich jene
schlussfolgernde Rechnung als einen nothewendigen Bestandtheil einer
Begriffsschrift anerkenne.''
In a lucid way the relations between Begriffsschrift, Boole's algebra and
Leibniz's characteristic are discussed in [Frege 1880], a text published
in [Kreiser (ed) 1973].}
\subsection %%1.3 -------------------------
{On a perspective in which there is no second origin}
I am aware of some, so to speak, unexpectedness of the contention that
there is more than one origin in modern logic.
My point may so appear because of some influential textbooks on
the history of logic in which Turing's results are unnoticed, likewise
those of Church, Kleene, Post, etc. It does not seem likely that the
authors were ignorant of these results; rather, they did not attach to
them a greater value, hence they perceived the developmnet of logic in a
very different perspective.
In Boche\'nski's {\it Formale Logik} Alonzo Church is mentioned only as a
historian of logic, never on account of his achievements in logic itself;
in the extensive Bibliography no mention is made of his seminal ``Note on
the {\it Entscheidungsproblem}'' and related papers. Turing does not exist
at all, either in Bibliograhy or in the body of the book. No mention is
found about J.\ Herbrand even in Bibliography where is a section listing
works related to Hilbert and formalism, among which Herbrand's should
be included as most significant (instead, there are items on Hilbert and
psychology, Hilbert and Husserl, etc.); Herbrand's fundamental study in
proof theory appeared in Poland in 1930, the time of Boche¤ski's academic
activity in the same country. That the issues studied by Hilbert, G\"odel,
etc.\ were alien to Boche\'nski's perspective is additionally confirmed in
Subject Index where no mention is made of recursive functions, decision
problem, etc.
Similar gaps occur in Kotarbi\'nski's lectures on the history of logic
[1964]. Turing does not appear there at all, Church is mentioned once,
only as the author of an encyclopedic entry, Herbrand is absent too;
Hilbert is referred to only once, in the context of philosophy of
mathematics. The problem of decidability is reported in one brief
paragraph, concerning G\"odel, and not mentioned any more.
Such an approach may be intepreted in the light of what we find in some
academic courses of logic as addressed to a wider audience. For instance,
a lucid textbook by Richards, 1978, does not bother about the decision
problem likewise other properties of deductive theories. The author's
intention seems like that of some 17th century textbooks on logic, which
promised an improvement of reader's mind. Such a selection of topics in
logic seems to be guided by evaluation related to a didactic bias, and that
may have inluenced the perspective of the two historians mentioned above.
\subsection %%1.4. ------------------------------
{The right perspective}
There appears a different landscape if we take {\it Development of
Logic} by W.Kneale and M.Kneale, 1962. Hilbert's programme and his
technical contributions, the revolutionary work of G\"odel, the
decidability issues, are the subjects treated extensively and thoroughly.
A due justice is done to Turing, though when discussing the impossibility
of a universal decision procedure for first-order logic, the authors
follow a simpler argument constructed by Tarski, Mostowski and Robinson,
1953, based on Tarski's work of 1933. The crucial role played by the
discoveries of the thirties if duly acknowledged, and Frege's work is
shown as the one from which there starts the development of modern logic.
As for a more detailed periodization of modern logic, one should look for
presentations dealing with modern logic alone. There are at least two such
works, completing each other. J. van Heijenoort's {\it From Frege to
G\"odel} is a source book. The sources are carefully commented by the
Editor who in Preface evidences his point that the period in
question is a historical whole in which G\"odel's results ``make year 1931
a fitting terminal date'' (p. vii). In the time point in which that book
ends, there starts the story told in [Mostowski 1965], covering the period
from G\"odel's results to the sixties. Thus each of these books confirms
the other in the claim that a new period of modern logic starts in the
thirties.
The same has been stated by [Post 1994, fn.\ 12] as follows.
\begin{quote}
``The creativeness of human mathematics has a counterpart inescapable
limitations thereof -- witness the absolutly unsolvable (combinatory)
problems. Indeed, with the bubble of symbolic logic as universal logical
machine finally burst, a new future dawns for it as the indispensable means
for revealing and developing those limitations. For Symbolic Logic may be
said to be Mathematics self-conscious.''
\end{quote}
Post's phrase ``a new future'' is what has been rendered as ``the second
origin'' in this paper.
There is no need to argue about the exact date of the second origin,
if we only agree to put it in the interval 1931-1943 (as motivated above,
at the end of the introductory comment). Then the choice of 1936 marks the
significance of the whole period, having been centered around that year
which enjoyed the greatest confluence of ideas.
The authors quoted above (van Heijenoort, Mostowski, Post) could not
possess that perspective which comes at the end of this century. In this
perspective, the results concerning decidability, and specially those
stated in terms of Turing machine, are of utmost consequence for the
philosophical foundations of science; moreover, they impact on AI research
and computational technology. Thus in either respect they constitute a
vital factor of the present and future civilization; this is a way in
which Post's utterance ``a new future dawns for logic'' can be interpreted.
\subsection{The idea of logic as embodied in Begriffschrift}
%%1.5 -----------------------------
Thus the year 1936 put end to the Leibnizian dream of universal
characteristic in the role of {\it filum cogitationis} -- the thread of
thought -- which was to be the tool of {\it ars inveniendi}. Let us use
Leibniz's statements to create a contrastive background to what emerged as
the second origin of logic.
Leibniz was dominated by the vision of a foolproof logic of dicovery
which, he believed, would be attained with the advances towards a perfect
language, to wit the projected by him {\it characteristica universalis}.%
\footnote
{Leibniz's statements like this quoted here express his firm endorsing of
what is now called {\it strong AI} in its representationist version. This
may seem strange in the view of his infinitist ontology which should imply
that the infinite cognitive content of the universe would be never matched
by the human mind, even equipped with the most powerful, but ever (ex
definitione) finite algorithms. That remarkable split deserves a closer
attention of Leibniz scholars (cf.\ [Marciszewski 1996].)}
Here are his words (commented in square brackets by the present author).
\begin{quote}
``With the passage of time, certain operations which were once
combinatorial [i.e., found with random combinations, and assessed as
valuable by the inspecting mind] will become analytic [i.e., obtained
algorithmically] after everyone has become familiar with my method of
combination, [here, no random combination, but guided in an algorithmic
way] which is within the grasp of even the dullest. This is why, with the
gradual progress of the human species, it can come about, perhaps after
many centuries, that no one will be any more praised for accuracy of
judgment; for the analytic art (which is virtually confined to mathematics
in its correct and general use) will have become universal and applied to
every type of matter through the introduction of a scientific notation or
`philosophical character' such as I am working on. Once this has been
accepted, correct reasoning, given time for thought, will be no more
praiseworthy than calculating large numbers without any error.'' [Couturat
1903, 168], translation in [Ross 1984, p.\ 62].
\end{quote}
Frege might have not endorsed that radical point that the ideal langauge
should make mathematical research ``within the grasp of even the dullest''
(which fittingly describes computers). Nevertheless, his project renders
his idea of logic, shared by the whole pre-G\"odelian generation of
logicians. Logic was commonly expected to be -- to recall Post's
expression (see above, 1.4) -- ``the universal logical machine''. Though
such a destiny of it was most firmly declared by Hilbert, its germs are
latent in the subtitle of {\it Begriffsschrift} which contains the notions
of pure thought and symbolic language, the latter having been meant as an
adequate representation of the former.
`Pure thought' was to express the idea of the independence from empirical
knowledge. This, in turn, implies that logic does not deal with any
particular domain given in empirical evidence, hence it enjoys a universal
range -- like Leibniz's universal characteristic. Taken in itself, this
notion does not decide if there exists an adequate symbolism to express
the totality of pure thought. However, the intention declared in the title
of Frege's masterpiece seems to convey the answer in the affirmative. This
would mean that any problem appearing in the pure thought could be
formulated in the given symbolism, while the answer could be deduced from
the axioms of the logical system expressed in this symbolism.
When that goal proved to be an unattainable phantom, this was a dramatic
change in the very foundations. Logic which emerged from that revolution
was not longer the same logic, imagined by Leibniz and striven for by
Frege. Like every genuine revolution, it must have matured in an
intensive process. Let us trace its main points.
\section %%2
{On paving the way to the second origin}
\subsection{The problem of solvability attacked by modern logic}
%%2.1 -----------------------------
Since Aristotle logic pretended to be a universal device to solve any
scientific problem with deductive reasoning. The riddle of solvability
appeared with the paradoxes of the ancients, especially the antinomies
concerning infinity. They were felt as something hardly soluble, hence
Greek mathematicians preferred to omit the problem than to attack it.
Christian theologians may have been the first to reflect on the problem
for their concern to distinguish the issues common to reason and
faith (as the existence of God) from those, called mysteries, which could
not be solved by human reason. There was a debate on some dogmas, for
instance whether that of the Holy Trinity can be demonstrated by reason
alone. Before the answer in the negative has become commonly accepted,
there were theologians, as Ramon Lull, who claimed the demonstrability of
that tenet.%
\footnote{Lull's logical {\it ars magna} was meant as a device to
rationally convince Muslims about God's being in trinity (cf.
Marciszewski, Murawski 1995).}
Though scientists sticked to the claim that any properly stated scientific
problem is capable of solution, the very concept of unsolvability was
present in the Western culture owing to the permanent tension between
science and religion.
Something like mysteries, indeed, appeared as antinomies in mathematics by
the end of the 19th century. This induced a new epistemological concept --
that of the {\it security} of a solution. Apart from varieties of
constructivism, Hilbert believed that maximal cognitive security is
provided by axiomatization and formalization.
In this respect, Frege contributed very much by axiomatization of logic,
and Peano in 1899 by axiomatization of arithmetic. Morever, geometry was
axiomatized by Hilbert and set theory by Zermelo. How axiomatization does
increase cognitive security is exemplified in the story of the axiom of
choice (if one refuses to trust the axiom, a similar distrust attaches
its consequences).
Moreover, new tools must have been devised to enable proving of the
fundamental theorems concerning incompleteness of arithmetic as well as
completeness and undecidability of first-order logic. These methods
include the techniques of formalization (Post, Hilbert, Hilbert, Tarski),
the methods of eliminating quantifiers (Skolem, Herbrand, Gentzen,
Hilbert), and numerical encoding of formulas (Finsler, G\"odel, Turing).
The accumulating of devices was combined with the Hilbertian incentive to
find a general method of solving mathematical problems.
\subsection{Hilbert's Entscheidungsproblem as the guiding idea}
%%2.2 ----------------------------------------
David Hilbert's call {\it in Mathematik gibt es kein Ignorabimus} was the
challenge issued at the Congress in Paris in 1900. It consisted, as stated
by [Hilbert and Ackermann 1928], in solving the {\it Entscheidungsproblem}
for first-order logic. The authors wrote as follows in the chapter dealing
with first-order logic (this is the passage which Turing refers to in
section 11 of his famous 1936 paper).
\begin{quote}
``The solution of the decision problem consists in knowing a procedure
which for any logical formula enables a decision concerning its validity
or satisfiability. This solution has fundamental importance for those
theories (in any field of research) whose theorems can be derived from a
finite set of axioms.''%
\footnote
{The original statement in ch.\ 3, sec.\ 11, p.\ 73 (omitted in the
English 1950 version, hence translated ad hoc by WM) runs as follows.
``Das Entscheidungsproblem ist gel\"ost, wenn man ein Verfahren kennt, das
bei einem vorgelegten logischen Ausdruck durch endlich viele Operationen
die Entscheidung \"uber die Allgemeing\"ultigkeit bzw.\ Erf\"ullbarkeit
erlaubt. Die L\"osung des Entscheidungsproblems ist f\"ur die Theorie
aller Gebiete, deren S\"atze \"uberhaupt einer logischen Entwickelbarkeit
aus endlich vielen Axiomen f\"ahig sind, von grunds\"atzlicher
Wichtigkeit.''}
\end{quote}
Then some provability problems are discussed in that context in order to
show that the positive solution of the decision problem for the
first-order logic entails decidability of any finitely axiomatized
mathematical theory.
The argument runs as follows. Suppose, there is the question of whether a
sentence $B$ is a theorem of the theory $T$. Let $A$ be the conjunction of
all the axioms of $T$ expressed in the language of first-order logic. Then
$B$ is provable on the basis of $A$ provided that the implication {\it
A}$\to${\it B} is universally valid ({\it allgemeing\"ultig}) in the
first-order logic (as providing mathematics with a universal language).
Were this logic decidable, any conditional formula like {\it A}$\to${\it
B} could be recognized either as being or as not being universally valid.
In the former case, $B$ would be provable from the axioms $A$ of $T$; in
the latter, the relation of provability would not hold, and thus $B$ would
not belong to $T$. Thus the solution of the Entscheidungsproblem for
first-order logic would bring about the following: if a formula is not
provable in the theory of question, then its unprovability could be
demonstrated with the means of first-order logic.
\section{The impact of reformed logic on intelligence research} %%3
\subsection{The confluence of ideas in 1936, Turing's position}
%%3.1 --------------------
Let us start from listing those titles, relevant to our problem, which
appeared in the same year 1936:\\
1) Alonzo Church: An unsolvable problem of elementary number theory; \\
2) Alonzo Church: A note on the Entscheidungsproblem; \\
3) Stephen C.\ Kleene: General recursive functions of natural numbers; \\
4) Emil L.\ Post: Finite combinatory process-Formulation -- 1; \\
5) Alan M.\ Turing: On computable numbers, with an application to the
Entscheidungsproblem.
All of them address the same question of how to precisely define the
intuitive notion of computability, when achieving this goal in different
ways: Church with his lambda-calculus, Kleene with the notion of recursive
functions, while Post and Turing with the notion of a machine (now called
``Post machine'' and ``Turing machine'', respectively).
Church's [1936a] paper is followed by the famous ``Note'' [1936b] being a
short corollary to the former text in which, on the basis of the
definition of calculabity, Church has shown that the general case of the
{\it Entscheidungsproblem} is usolvable in any system which is adequate to
a certain portion of arithmetic and is $\omega$-consistent.%
\footnote
{The general case of the decision problem is meant in
contradistinction to special cases as those studied in [Ackermann
1954].}
The ``Note'' quotes the theorem following from [Church 1936a]: {\it The
general case of the Entscheidungsproblem of the the system L (i.e.,
first-order logic with equality and suitable arithmetic notions) is
unsolvable.} Then, using that theorem together with the method of
translating a mathematical theory into the language of first-order logic,
as that in [Hilbert and Ackermann 1928], Church shows that {\it the
general case of the Entscheidungsproblem of first-order logic is
unsolvable.}
The argument runs as follows. Suppose, there exists a general decision
procedure for first-order logic. Then for any conditional $A\to F$ ($A$
being the conjunction of arithmetical axioms), when translated into the
language of first-order logic, one can decide whether this conditional is
valid or not. Provided that $A\to F$ is valid, then there is a correct
proof of $F$ on basis of $A$; is it not valid, then there is no proof.
Thus the supposition that first-logic is decidable leads to the conclusion
that arithmetic is decidable too, and that contradicts G\"odel's and
Church's (his previous paper) results.
There are good reasons to complete the above list by the
following two publications that also appeared in 1936: \\
6) Kurt G\"odel: \"Uber die L\"ange von Beweisen;\\
7) Alfred Tarski: \"Uber den Begriff der Logischen Folgerung.
The concise communication by G\"odel conveys the following message, which
is of consequence also for current projects of practical (e.g., that
for the purposes of databases) formalization of mathematics.
\begin{quote}
``Let the system $S_i$ contain variables and quantifiers for natural
numbers, for classes of natural numbers, for classes of classes of natural
numbers, and so on, but no variables of a higher type. Then there are
obviously sentences from $S_i$ which are provable in $S_i+1$ but not in
$S_i$. [...] {\it The transition to logic of the next higher level brings
about not only that certain earlier unprovable sentences become provable,
but also that infinitely many of the already existing proofs can become
extraordinarily shortened.}'' [P.\ 23, italics G\"odel's, ad hoc
translation by WM.] \end{quote}
This result makes a considerable impact on intelligence research. The
power of reasoning constitutes a major part of intelligence, and the
result in question is concerned with ever higher degrees of that power.
This seems to open a lucky perspective for automated reasoning, at least
in mathematics. However, it may be asked whether the sequence of logics
of ever greater deductive power, as represented by ever greater ordinals,
is complete in the sense that to any problem $A$ there corresponds an
ordinal $\alpha$ such that $A$ is solvable by means of the logic
$L_\alpha$.
The issue was faced by Turing [1939] who obtained some partial results but
did not find an answer to the main question. If some day someone succeeds in
finding answer in the affirmative, this will be a great day for AI
research. Some attempts in this direction are being made, as told in
[Feferman 1988].
So much as to the story which started with [G\"odel 1936]. As to Tarski's
1936 paper on logical consequence, its contribution to intelligence
research depends on observing that inference rules of first-order logic
do not exhaust the set of all the rules used in mathematical reasoning as,
e.g., the rule of infinite induction. This is the fact which by [Beth
1955] has been fittingly rendered in the opposition of {\it formal
derivability} and {\it semantic entailment}; the latter is by Tarski
called {\it logische Folgerung}. Now the question arises: whether
artificial deduction (as a part of AI) has to be confined to formal
derivability, or can it succeed in semantic entailment? Before the
discoveries of the period 1931-1936, in which Tarski played a
significant role, no such question could be stated.
As to the question of the prospects of AI, including those of mechanical
deduction, Turing's approach proves most convenient. His notion of a
machine yields a conceptual framework to compare computers and brains;
both can be considered as information procesing systems equipped with
memory, processing units, reading units etc. In such terms one can make
obsevations and put questions of how to create artificial and improve
natural intelligence, according to Winston's maxim (see footnote 2).
Having had got a colossal experience in using cryptography machines
during the Second World War, when running the main British intelligence
unit for deciphering German Army codes, Turing came to the idea of an
intelligent machine. The interplay of two senses of the English word
``intelligence'' proved inspiring: those enormous military intelligence
tasks required highly intelligent machines, indeed, and Turing had
opportunity to realize that such machines would be no Utopia.
In 1948 Turing delivered a technical raport entitled ``Intelligent
Machinery'' to discuss possible ways in which machines might be made to
show intelligent behaviour; the analogy with the human brain was used as a
guiding principle. This raport should be acknowledged as the beginning of
AI research.
\subsection{Does Church-Turing Thesis apply to the physical world?}
%%3.2 ----------------------
{\it The class of functions which are computable in the informal intuitive
sense is identical with the class of Turing (or Post) computable
functions.} Instead of {\it Turing computable} (capable of being computed
by a Turing machine) any of the following terms can be used: recursive,
representable, lambda-definable, etc. The equivalence of the listed
classes was proved by Church, Turing and others. The equivalence of
each of them with the class of functions being computable intuitively,
that is, in accordance with the common mathematical practice, is
conjectured by Church-Turing Thesis (italicized above).%
\footnote
{The name of the thesis is often abbreviated to the form ``Church Thesis''
though its authorship is shared by Turing. To emphasise Turing's role in a
debate concerning the Thesis, I use its full name. A concise treatment of
the Thesis and related issues is found in [Krajewski 1981], a more
extensive one in [Grzegorczyk 1974].}
As observed by [Rosen 1998], the essence of Church-Turing Thesis is
that it identifies {\it logical inference} with {\it string processing},
that is, with a purely syntactic activity. Logical inference is what is
defined in first-order logic, and string processing is exactly what
Turing machines do.%
\footnote
{Logical inference should not be mistaken for logical consequence in
Tarski's [1936] sense, the letter being a semantic relation.}
In the light of G\"odel's and Tarski's discoveries, there are truths which
cannot be obtained through logical inference in the above-mentioned sense.
Let the reasoning with which such truths are attained be called {\it
extralogical inference.} Such inferences must have an unformalizable
semantic component. That extralogical inferences do exist in mathematics
is an undubitable mathematical result, but the problem arises whether they
should appear in our thinking of the empirical world. The answer in the
negative is a possible complement of Church-Turing Thesis, pioneered by
Turing himself (while Church remained neutral in the resulting debate);
let us call it the {\it finitist conjecture} --- FC, for short.
The present essay does not argue either for or against FC. As a historical
study, it is to recognize the stucture of a historical process, to wit the
evolution of modern logic. It evidences that the turning point in this
evolution consists in defining a class of mutually related
metamathematical concepts --- computability, decidability, etc. The great
significance of Church-Turing Thesis consists in its following feature:
for the first time in the history of logic its so abstract conceptual
apparatus is engaged in putting questions concerned with the physical
world.
The meaning of FC can be explained in two ways: \\
(1) by analyzing procedures of computer simulation, \\
(2) by discussing the hypothesis that the brain is nothing more than a
Turing machine.
Item 1 results in the following issues:
(1a) the problem of how does simulation approximate an actual process,
(1b) the problem of mechanizing the operations of encoding and decoding
in the process of simulation.
Here the encoding consists in recording physical data in arithmetical and
logical symbols, e.g., representing causal relations by implications,
as in that trivial example: if it rains, then streets are wet.
FC replies to question 1a as follows: a complete simulation (i.e., one
that does not reduce to an approximation) is possible, in principle.
Whether we attain it, is just a question of computational power and of
time being available. In other words, the complexity of any simulated
physical process is finite. Though this issue does not belong to logic but
to a theory of physical world, the rise of questions like 1a is due to
logic, as shaped in the phase 1931-1936. The opposite conjecture, denying
FC, is to the effect that there are relations in the world which would
be fully rendered only by real functions or even (a more radical point)
non-computable fuctions ([Myhill 1966], [Barrow 1991, chapt.\ 10],
[Penrose 1989], [Bunge 1993]).
Problem 1b results in the following exercise. After physical data are
encoded, they are processed according to some Turing machine rules. Let
the processing robot be called $R_0$. The encoding itself cannot be
carried out by $R_0$. However, if FC is right, the operations of encoding
and decoding can be carried out by other robots. Suppose, we employ for
encoding the robot $R_1$. It is now up to him (it?) to encode physical
data, say, to render the concept of causality with an implication formula,
the falling of an apple with Netwon's gravitation formula, and so on; thus
the whole knowledge of Laplace's daemon could be adequately represented in
enormously long but finite strings of zeros and ones. However, somebody
must have programmed $R_1$, that is, to load his memory with a code being
a metalanguage with respect to the languages both of physics and logic with
arithmetic. Suppose, this has been done by the robot $R_2$. Actually that
task is being performed by humans, and these are programmed for it, so to
speak, by evolution. But FC says that humans are not necessary since any
problem whatever can be solved by a robot. Now it is up to FC believers to
design the further (after the step made by $R_1$) encoding and decoding
procedures.
Problem 2 is concerned with nature of a living system, in particular the
human brain. The pioneering work [McCulloch, Pitts 1943] initiated looking
at the brain as a logical machine. If it is the case, as FC claims, that
all processes in nature can be adequately simulated by Turing machines,
then the computational power of brain processes, as being a part of
nature, cannot exceed the power of Turing machine. This, in turn, implies
that any neural process is a string of symbols, that is, spatial objects
which are processed according to strict rules for the purpose of solving a
problem. If neurobiology takes the universal Turing machine for an
adequate model of the brain, it will face the following challenges: \\
$\bullet$ to find out all the kinds of neural processes and define each of
them -- as a string of symbols -- according to the kind of problem to be
solved by the process in question; \\ $\bullet$ to discover the alphabet
of symbols, and the rules according to which their strings are formed and
processed in order to solve a given problem; let this system be called a
neural language; \\ $\bullet$ to discover rules of converting expressions
of the neural language into those of a language used by people for
communication.
The last listed task may be exemplified as follows. Imagine a person who
carries out calculations on a sheet of paper, hence in an external discourse
(including numerals, function signs, etc.), while at the same time in this
person's brain there occurs a process in the neural language to control
that occurring in the paper-written discourse. There must exist rules to
coordinate symbol strings of one of these languages to the corresponding
strings in the other. Since paper calculations form a typical case of
Turing machine (Turing called it ``paper machine''), their exact mapping
onto a neural process would support the claim that the brain is a machine
according to Turing's design.%
\footnote
{The problem of relation between the neural language and that of
historically evolved language of logic and mathematics has drawn von
Neumann's attention in his essay [1958]. A discussion of von Neumann's
suggestions is given in [Marciszewski 1994] where it is claimed that
standard logic should be completed with a knowledge of neural processes
for the sake of communication theory (called there rhetoric).}
Let me conclude with a witty remark of the British physicist and
astronomer John Barrow, who so points up the logical discoveries of the
thirties. {\it Since religion is what demands the belief in unprovable
truths, mathematics is the only intellectual system able to prove that it
is a religion.} Are some future machines able to produce such mathematics?
If they are, they should become partners of humans. If not, they will
remain ingenious tools for computing computable functions.
\begin{thebibliography}{{}}
\bibitem[Ackermann] {{}} W.\ Ackermann, {\it Solvable Cases of the
Decision Problem.} North-Holland, Amsterdam 1954.
\bibitem[Barrow 1991] {{}} J.\ D.\ Barrow {\it Theories of Everything: the
Quest for Ultimate Explanation.} Oxford Univ.\ Press, New York 1991.
\bibitem[Beth 1955] {{}} E.\ W.\ Beth, {\it Semantic Entailment and Formal
Derivability.} Noord-Hollandsche, Amsterdam 1955.
\bibitem[Boche\'nski 1956] {{}} J.M.\ Boche\'nski, {\it Formale Logik}.
Alber, M\"unchen.
\bibitem[Boden (ed) 1990] {{}} M.\ A.\ Boden, {\it The Philosophy of
Artificial Intelligence.} Oxford University Press, Oxford 1990.
\bibitem[Brzezi\'nski et al.(eds)] {{}} J.\ Brzezi¤ski, S.\ Di Nuovo, T.\
Marek, T.\ Maruszewski, {\it Creativity and Consiousness: Philosophical
and Psychological Dimensions.} Editions Rodopi, Amsterdam etc.\ 1993.
\bibitem[Bunge 1993] {{}} M.\ Bunge, Explaining creativity. In:
[Brzezi\'nski et al.(eds)].
\bibitem[Church 1936a] {{}} A.\ Church, An unsolvable problem of
elementary number theory. {\it Am.\ J.\ Math.} {\bf 58}, 1936, 345-363.
\bibitem[Church 1936b] {{}} A.\ Church, A note on the Entscheidungsproblem.
{\it J.\ of Symbolic Logic} {\bf 1}, 1936, 40-41, 101-102.
\bibitem[Couturat (ed) 1903] {{}} L.\ Couturat (ed), {\it Opuscules et
fragments in\'edits de Leibniz.} Paris 1903.
\bibitem[Davis (ed) 1993] {{}} M.\ Davis (ed), {\it Solvability,
Provability, Definability. The Collected Works of Emil L.\ Post.}
Birkh\"aser, Boston etc.\ 1993.
\bibitem[Feferman 1988] {{}} S.\ Feferman, Turing in the land of (O)z.
In: [Herken (ed) 1988].
\bibitem[Frege 1879] {{}} G.\ Frege, {\it Begriffsschrift, eine der
arithmetischen nachbildete Formelsprache des reinen Denkens}. L.\ Nebert,
Halle 1879.
\bibitem[Frege 1880] {{}} G.\ Frege, Booles rechnende Logik und die
Begriffsschrift. Unpublished text dated 1880/1881, included in: [Kreiser
(ed) 1973].
\bibitem[Frege 1883] {{}} G.\ Frege, \"Uber den Zweck der Begriffsschrift.
2.\ Sitzung an 27.\ Januar 1882. {\it Sitzungsberichte der Jenaische
Gesellschaft f\"ur Medizin und Naturwissenschaft f\"ur das Jahr 1882},
{\bf 16}, Supplement, 1-10. Gustav Fischer, Jena 1883.
\bibitem[G\"odel 1930] {{}} K.\ G\"odel, Die Vollst\"andigkeit der Axiome
des logischen Funktionenkalk\"uls.
{\it Monatshefte f\"ur Mathematik und Physik}, {\bf 37}, 1930, 349-360.
\bibitem[G\"odel 1931] {{}} K.\ G\"odel, \"Uber formal unentscheibare
S\"atze der {\it Principia Mathematica} und verwandter Systeme -- I.
{\it Monatshefte f\"ur Mathematik und Physik}, {\bf 38}, 1931, 173-198.
\bibitem[G\"odel 1936] {{}} K.\ G\"odel, \"Uber die L\"ange der Beweisen.
{\it Ergebnisse eines mathematischen Kolloquiums}, Heft 7 [containing the
papers read in] 1934-35, Franz Deuticke, Leipzig und Wien 1936.
\bibitem[Grzegorczyk 1974] {{}} A.\ Grzegorczyk, {\it An Outline of
Mathematical Logic}, Reidel and PWN, Dordrecht and Warsaw, 1974.
\bibitem[Herbrand 1930] {{}} J.\ Herbrand, {\it Recherches sur la
th\'eorie de la d\'emonstration.} La Soci\'et\'e des Sciences et des
Lettres de Varsovie, Warszawa [Warsaw, Poland] 1930.
\bibitem[Herken (ed) 1988] {{}} R.\ Herken (ED), {\it The Universal
Turing Machine. A Half-Century Survey,} Oxford Univ.\ Press, Oxford 1988.
\bibitem[Hilbert 1900] {{}} D.\ Hilbert, Mathematische Probleme. Vortrag,
gehalten auf dem internationalen Mathematiker-Kongress zu Paris 1900. {\it
Archiv der Mathematik und Physik,} 3rd series, {\bf 1}, 1901, 41-63, 213-237.
\bibitem[Hilbert, Ackermann 1928] {{}} D.\ Hilbert und W.\ Ackermann, {\it
Grundz\"uge der theoretischen Logik.} Julius Springer, Berlin 1928.
English version {\it Principles of Mathematical Logic}, Chelsea, New York
1950, ed.\ by R.\ E.\ Luce is based on 2nd German edition, 1938.
\bibitem[Kneale 1962] {{}} W.\ Kneale and M.\ Kneale, {\it The Development
of Logic.} Clarendon Press, Oxford 1962.
\bibitem[Kotarbi\'nski 1964] {{}} T.\ Kotarbi\'nski, {\it Le\c{c}ons sur
l'histoire de la logique.} Presses Univ.\ de France, Paris 1964.
\bibitem[Krajewski 1981] {{}} S.Krajewski, Recursive functions. In:
[Marciszewski (ed) 1981].
\bibitem[Kreiser (ed) 1973] {{}} L.\ Kreiser, {\it Gottlob Frege:
Schriften zur Logik. Aus dem Nachla{\ss}}. Akademie-Verlag, Berlin 1973.
\bibitem[Leibniz] {{}} see [Couturat 1903].
\bibitem[Marciszewski (ed) 1981] {{}} W.\ Marciszewski, {\it Dictionary of Logic
as Applied in the Study of Language. Concepts / Methods / Theories.}
Nijhoff, The Hague etc.\ 1981.
\bibitem[Marciszewski 1994] {{}} W.\ Marciszewski, {\it Logic from a Rhetorical
Point of View.} de Gruyter, Berlin etc.\ 1994. Series ``Grundlagen der
Kommunikation und Kognition'' ed.\ by R.\ Posner and G.\ Meggle.
\bibitem[Marciszewski, Murawski 1995] {{}} W.\ Marciszewski and R.\
Murawski, {\it Mechanization of Reasoning in a Historical Perspective.}
Editions Rodopi, Amsterdam 1995.
\bibitem[Marciszewski 1996] {{}} W.\ Marciszewski, H\"atte Leibniz von
Neumanns logischen Physicalismus geteilt?, {\it Beitr\"age zur Geschichte
der Sprachwissenschaft}, {\bf 6.2}, 1966, 245-260. A modified English
version ``Leibniz's Two Legacies -- Their Implications for
Knowledge Engineering'' in {\it Knowledge Organization}, {\bf 23},
No.2, 1996, 77-82. See also the same author's ``Why Leibniz should not
have believed in {\it filum cogitationis}?'' in: {\it Leibniz und Europa.
VI.\ Internationaler Leibniz-Kongre{\ss}. Vortr\"age. I.\ Teil}, Hannover
1994, 457-464.
\bibitem[McCulloch, Pitts 1943] {{}} W.\ S.\ McCulloch and W.\ Pitts, A
logical calculus of the ideas immanent in nervous activity. {\it B.\
Math.\ Biophy.} {\bf 5}, 1943, 115-133. Reprinted in [Boden (ed) 1990].
\bibitem[Mostowski 1965] {{}} A.\ Mostowski, {\it Thirty Years of
Foundational Studies: Lectures on the Development of Mathematical Logic
and the Study of the Foundations of Mathematics in 1930-1964.} Soc.\
Philos.\ Fennica (Acta Philos.\ Fennica 17), Helsinki 1965.
\bibitem[Myhill 1966] {{}} J.\ Myhill, Creative computation revisited.
{\it USAF Technical Report,} 1966.
\bibitem[Penrose 1989] {{}} R.\ Penrose, {\it The Emperor's New Mind:
Concerning Computers, Minds, and the Laws of Physics.} Oxford Univ.\
Press, Oxford etc.\ 1989.
\bibitem[Post 1936] {{}} E.\ L.\ Post, Finite combinatory process ---
Formulation I. {\it J.\ of Symbolic Logic} {\bf 1}, 1936, 103-105.
Reprinted in: [Davis (ed) 1994].
\bibitem[Post 1994] {{}} E.\ L.\ Post, Absolutely unsolvable problems and
relatively undecidable propositions --- account of an anticipation. In:
[Davis (ed) 1994].
\bibitem[Richards 1978] {{}} T.\ J.\ Richards, {\it The Language of
Reason.} Pergamon Press, Oxford etc.\ 1978.
\bibitem[Rosen 1988] {{}} R.\ Rosen, Effective processes and natural law.
In: [Herken (ed) 1988].
\bibitem[Ross 1984] {{}} G.\ MacDonald Ross, {\it Leibniz.} Oxford Univ.\
Press, Oxford etc.\ 1984.
\bibitem[Tarski 1933] {{}} A.\ Tarski, {\it Der Wahrheitsbegriff in den
formalisierten Sprachen.} In the series: {\it Studia Philosophica}, {\bf 1},
1936 [1933 is the date of publishing the Polish original by
La Soci\'et\'e des Sciences et des Lettres de Varsovie]. English
translation: The Concept of Truth in Formalized Languages in: A.\ Tarski,
{\it Logic, Semantics, Metamathematics. Papers from 1923 -- 1938,}
Clarendon Press, Oxford 1956.
\bibitem[Tarski et al.\ 1953] {{}} A.\ Tarski in collaboration with A.\
Mostowski and R.\ M.\ Robinson, {\it Undecidable Theories.} North-Holland,
Amsterdam 1953.
\bibitem[Turing 1936] {{}} A.\ Turing, On computable numbers, with an
application to the Entscheidungsproblem. {\it Proc.\ of the London Math.\
Society,} Series 2, {\bf 42}, 1936, 230-265.
\bibitem[Turing 1939] {{}} A.\ Turing, Systems of logic based on ordinals.
{\it Proc.\ of the London Math.\ Society,} Series 2, {\bf 45}, 1939,
161-228.
\bibitem[Turing 1948] {{}} A.\ Turing, Intelligent machinery --- Raport,
National Physics Laboratory. In: B.\ Meltzer and D.\ Michie (eds), {\it
Machine Intelligence} {\bf 5}, Edinburgh Univ.\ Press, Edinburgh 1969.
\bibitem[Turing 1950] {{}} A.\ Turing, Computing machinery and intelligence.
{\it Mind} {\bf 59}, 1950, 433-460. Reprinted in: [Boden 1990].
\bibitem[van Heijenoort 1967] {{}} J.\ van Heijenoort, {\it From Frege to
G\"odel. A Source Book in Mathematical Logic.} Harvard Univ.\ Press,
Cambridge (Mass.), London 1967.
\bibitem[von Neumann 1958] {{}} J.\ von Neumann, {\it The Computer and
the Brain,} Yale Univ.\ Press, New Haven 1958.
\bibitem[Winston 1984] {{}} P.\ H.\ Winston, {\it Artificial Intelligence,}
Addison-Wesley, Reading etc.\ 1984 (3rd ed.\ 1992).
\end{thebibliography
\end{document}