ISE 2003 Invited Keynote Speech

 

 

Computation and Information: Two Sides of the Same Coin

 

J. Michael Dunn

School of Informatics

Indiana University

Bloomington  IN  47408  USA

 

 

 

Abstract of Presentation:

The use of binary accessibility relations on states in providing models for some aspects of computation is well known, one of the best examples being Pratt's dynamic logic.  The relation is something like “given that the system is in State 1, then State 2 can result.”  Pratt implicitly uses a ternary relation, since each accessibility relation is indexed by the program being executed.  We generalize this by the use of an “untyped” ternary accessibility relation on states.  One is to think of a ternary relation still as in effect an indexing of binary relations, but this time the “subscript” is a state rather than a program.  One reads it something like “given that the system is in State 0, then if the system were to go into State 1, then State 2 could result.” 

 

It might be argued that all the information that is relevant to possible transitions is contained in State 1 alone, and so there is no reason to consider the “perspective” of State 0.  Indeed, on a deterministic conception of computation, the initial state would uniquely determine all of the subsequent states.  But this objection overlooks the possibility of working with partial states, as we shall do.  (Pratt used total states, but non-deterministic programs.)

 

It is well known that a set of states A can be thought of as a “proposition” (the set of states in which it holds).  So A is quite static.  But, and this is the main idea, it can be turned in for the set of relations determined by those states, and those relations can of course be regarded as transformations of states.  So, A is at the same time quite dynamic. 

 

The purpose of this talk is to present and expand upon some ideas from Dunn (2001), which focused on the interplay between the static and dynamic aspects as just described, and made a case that they represent a duality between information and computation.  Comparisons were made to Frege's object/concept distinction and to von Neumann's notion of a stored program.  Mathematically, these ideas arise from Dunn’s “gaggle” theory, which generalizes work of Jónssson and Tarski in representing Boolean algebras with operators.  Much of this earlier work is summarized in Dunn and Hardegree (2001). 

 

By R[A] let us mean the set of relations determined by the states in A.  Suppose we have two such propositions A and B.  We can then do various things with R[A] and R[B].  Thus, as one example, we can take R[A] and “apply” it to B, getting all the states we can get to from B using a relation in R[A], treating A as a program and B as data.  This is the key to modeling combinatory logic. 

 

This uses only the implicit relation character of A.  But we can use the implicit relational character of both A and B, taking the relations in R[A] and the relations in R[B] and forming their relative products in all possible ways.  This is like viewing both A and B as programs, and composing A with B.  This is the key to representing relation algebras.  Lyndon showed that relation algebras cannot be represented in the natural way by taking elements to be relations.  We in effect show this can be done one type-level higher, by taking elements to be sets of relations, i.e., a “relational database.” 

 

We also examine in this presentation the modeling of Pratt's dynamic logic and action algebras, Hoare's “Logic of Programs,” and Kleene algebras. 

 

We close with some speculations about what happens if we “subscript” positions in the ternary relation other than the first position, and also what happens if we allow relations of arbitrary degree.  Along the way, we discuss how to generalize (directed) graphs of binary relations to ternary relations and beyond using (directed) simplices.  In the case of a ternary relation this is just an equilateral triangle with one side an arrow (pointing to say the last position). 

 

References

J. M. Dunn (2001), “Ternary Relational Semantics and Beyond: Programs as Data and Programs as Instructions,” Logical Studies , no. 7, Institute of Logic, Russian Academy of Sciences, Special Issue: Proceedings of the International Conference Third Smirnov Readings (Moscow, May 24-27, 2001), part 2, http://www.logic.ru/LogStud/.

 

J. M. Dunn and G. Hardegree (2001), Algebraic Methods in Philosophical Logic, Oxford University Press. 

 

 

Biography of Speaker: 

J. Michael Dunn is Dean of the School of Informatics, Professor of Informatics, Professor of Computer Science, and Oscar Ewing Professor of Philosophy at Indiana University.  He has an A.B. in Philosophy from Oberlin College and a Ph.D. in Philosophy (Logic) from the University of Pittsburgh.  He taught at Wayne State University and at Yale University before moving to Indiana University in 1969.  He has chaired the Philosophy Department and been Executive Associate Dean of the College of Arts and Sciences.  He has been a Visiting Professor at the University of Melbourne, Oxford University, the Australian National University, Moscow State University, the University of Pittsburgh, and the University of Massachusetts. 

 

Dunn’s research interests include non-classical logics (especially substructural logics such as relevance logic and linear logic), algebraic logic, proof theory, relations between logic and computer science, and cryptography. 

 

He has been awarded grants from NSF and NEH, a Fulbright Research Fellowship, and an ACLS Fellowship.  He is the author of two books, edited two others, and has published eighty research articles.  He chaired the committee that in 1998 created the Five Year Strategic Plan for information technology at Indiana University. 

 

Dean Dunn serves on the board of the Indiana Pervasive Technology Labs, and the editorial Boards of Noûs, Studia Logica, Journal of Non‑Classical Logic, Taiwan Journal of the History and Philosophy of Science, e-Service Journal, and is North American Editor of the Bulletin of the Section of Logic of the Polish Academy of Sciences.  He has been an editor of The Journal of Symbolic Logic and chief editor of the Journal of Philosophical Logic.  He has been President of the Society for Exact Philosophy and a member of the Council and Executive Committee of the Association for Symbolic Logic.  He is a member of the Association for Symbolic Logic, American Philosophical Association, Society or Exact Philosophy, Philosophy of Science Association, Association for Computing Machinery, and IEEE Computer Society. 

 

Indiana University’s School of Informatics (http://informatics.indiana.edu) is the first school of informatics in the United States, and the first new school at Indiana University in 28 years.  The School just completed its third year of operation in 2002-2003.  Informatics is conceived as the study of the application of information technology to specific domains, together with a study of the commonalities of those applications (largely driven by the problems of large data sets).