Log Bank

For Polish version, formatted in TeX, click here.

INTERACTIONS BETWEEN LOGIC AND COMPUTER SCIENCE

Workshop for Logic, Informatics and Philosophy of Science
Held
In the Centenary of Emil Post's Birth (Augustow, Poland, 1897)
under the Auspices of Polish Association for Logic and Philosophy of Science
Bialystok, Poland, 13-14 December, 1997

Report by Witold Marciszewski

Any anniversary in the development of thought bears some relation to the origin of an idea. Even if someone's death is commemorated, this is because of his contributing something new to the development considered.

When celebrating an anniversary in the history of logic, we should recall that this history has two independent origins, and two interconnected lines of development.

Let the symbolic dates of either origin be 1879 and 1900: (i) the birth of modern logical calculus with Gottlob Frege's Begriffsschrift, and (ii) the start of inquiries into deductive theories with David Hilbert's challenge to prove the consistency of the real-number system (his address Mathematische Probleme at the Paris International Congress of Mathematicians). Though in that address he did not suggest any approach yet, it was the first statement of the problem which most influenced the development of logic in the 20th century.

Some logicians succeeded mainly in creating new important calculi, other ones contributed rather to Hilbert's line of inquiry. Not each of them, even among those most merited, was lucky enough to impact on both lines of research.

Emil Post was. His contributions to propositional calculi as well as results concerning decidability and recursion, also ideas seminal for computer science, belong to the highest achievements of modern logic. Hence it seemed worthwhile to take the opportunity of Post's birth centenary in order to survey some of the most vital problems of logic, and to assess the progress made since Post's time.

That such an initiative appeared in an academic circle of Bialystok (Poland) is due not only to the fact that Post was born in 1907 in vicinity of this town (being the capital of the region). There is a more relevant reason, to wit this circle's vivid interests in foundations of computer science and in automated reasoning, the latter having been, to some extent, presented in Nos.1, 2 and 3 of Mathesis Universalis.

The meeting to celebrate Post's centenary was meant as a workshop, that is, a forum for free discussion, exchange of ideas, application of skills, etc (according to Werner Heisenberg's dictum that Wissenschaft im Gespräch entsteht). Unfortunately, too short time available for preparations occasioned that it turned rather a typical conference consisting of a series of papers. Hopefully, next meetings to be organized by the same circle - as sketched by the end of this report - will more satisfy the definition mentioned. However, let me call it a workshop when continuing this report.

A survey of contributions

Here is the list of papers in the sequence of their delivering, the titles being translated from Polish, and sometimes commented, by the author of this Report. The comment to the introductory paper, by Roman Murawski, is submitted by its author.

• Roman Murawski: Emil L. Post and the development of mathematical logic and recursion theory.
  The paper deals with the following issues: (1) the meaning of results of Post's doctoral dissertation for the development of the metamathematical studies of propositional calculus, (2) the significance of his studies on canonical systems for the theory of formal languages as well as for the foundations of computation theory, (3) his anticipation of G\"odel's and Church's results on incompleteness and undecidability, (4) his results on the undecidabiity of various algebraic formal systems and finally (5) his contribution to establishing and to the development of recursion theory as an independent domain of the foundations of mathematics. The paper ends with some remarks on the philosophical and methodological background of his results.
• Grzegorz Malinowski: Post's multi-valued logics.
• Witold Marciszewski: Half-century of the project of intelligent machine and of mechanization of reasoning.
• Piotr Wojtylak: Axiomatizability of logical matrices.
• Marcin Mostowski: Computational semantics for monadic quantifiers.
• Andrzej Trybulec: Types, permissivness, and axiom of choice. -- The author of Mizar, a system of mathematical knowledge management with proof checker, stated some theorical reflexions based on Mizar team's experiences.
• Ewa Orłowska: Polish research in Post's logics. -- The paper concerned with research carried out in the circle of Helena Rasiowa to connect Post algebras with intuitionistic logic, logic of programs (esp. Salwicki's algorithmic logic), rough sets theory, etc.
• Jarosław Stepaniuk: Information processing with the method of rough sets.
• Zenon Sadowski: On a development of Post's ideas in structural computational complexity .
• Czesław Byliński: A formalization of the theory of categories.
• Jolanta Koszelew: Probabilistic algorithms vs Markov chains.
• Wiktor Dańko, Jolanta Koszelew: Post's correspondence theorem as a method of proving indecidability in logics of probabilistic programs.
• Slavian Radev: Argumentation semantics vs the logics of Post and of Lukasiewicz.

Organizational Affairs and a Further Outlook

The Workshop, first designed in the Chair of Logic, Informatics and Philosophy of Science of the University in Bialystok, was then co-organized and financially supported by the Institut of Computer Science, run by Wiktor Danko, of the Bialystok Technical University. There was also a considerable contribution of the Institute of Mathematics (University of Bialystok) run by Krzysztof Prazmowski.

This Workshop is meant to initiate a series of similar meetings in coming years. The idea of relating them to chosen anniversaries was expressed at the start of this report. Let it be added that the very choice of a date suggests a perpective in which one should see the development of logic.

The perspective accepted by the Chair of Logic (etc) of the University in Bialystok, shared by its partners as mentioned above, can be expressed in terms of the "second origin of logic", that of Hilbert's 1900 address. This should involve problems of formalization and mechanization of inferences and related issues of decidability. These topics have not only the obvious mathematical and computer-scientific significance but also a vital mind-philosophical import. All the three aspects should be taken into account in future workshops.

There are two centenaries in the coming years around which next meetings may be organized: the hundred years of Hilbert Programme, as counted since 1900, and the centenary of Alfred Tarski's birth in 2001. As for the latter, not only Tarski's great contributions to the decidability issues make that anniversary so relevant. Also his conception of logical (semantic) consequence should assist automated reasoning research in its brand oriented towards AI and cognitive science. For Tarski's concept is less restrictive than the theory of logical consequence based on the notion of logical tautology, hence better adjusted to commonsense reasoning.

A contrastive background to Tarski's concepts of truth and consequence is found in Hilbert School, especially in Jaques Herbrand's proof theory. At the same time, that theory belongs to the core of recent research in automated reasoning. It is, therefore suggested, that both Hilbert Programme, and Jaques Herbrand's contributions to it, as much relevant to automated deduction, be commemorated at workshops 1999 and 2000.

1998 is a proper year to commemorate the first statement of the project of Artificial Intelligence as made by Alan Turing in 1948 in his report Intelligent Machinery, where the role of automated reasoning is interestingly emphasized. This should be a continuation of Post Workshop as reported here, as there was a surprising confluence of Post's and Turing's ideas.

It does not seem necessary to look for other anniversaries after 2001. Problems and results issuing from the four-year research here projected should profit in next years as an abundant source of new problems, ideas, and results.