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}