Computability Logic (CL) is a logic of computational (and/or informational) resources and tasks, with these entities understood in their most general - interactive - sense. CL is a formal theory of computability in the same sense as classical logic is a formal theory of truth. This approach, initiated recently by the speaker, views interactive computational problems as a certain, highly relaxed, sort of games between a machine and the environment, and understands computability as existence of a machine that always wins the game. The definitions of the underlying concepts appear to yield an adequate formal counterpart of our intuition of speed-independent interactive algorithms, thus allowing us to generalize the Church-Turing thesis to an interactive level.

With logical operators representing certain most basic and natural operations on games, computability logic provides a powerful formal tool for studying interactive computational problems in a systematic way. Some of the other potential application areas include knowledge base systems, systems for planning and action, constructive applied theories.


Professor G. Japaridze got two Ph.D's: one from Moscow University in Logic and the other one from UPenn in Computer Science. His recent paper on Computability Logic has become the most downloaded paper of 2003 at the Annals of Pure and Applied Logic. Dr. Japaridze is a PI of an NSF grant on "A logical study of interactive computational problems understood as games".