Concept

Computability logic

Overview

Computability logic (CoL) is a research program and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic, which is a formal theory of truth. It was introduced and so named by Giorgi Japaridze in 2003.

In classical logic, formulas represent true/false statements. In CoL, formulas represent computational problems. In classical logic, the validity of an argument depends only on its form, not on its meaning. In CoL, validity means being always computable. More generally, classical logic tells us when the truth of a given statement always follows from the truth of a given set of other statements. Similarly, CoL tells us when the computability of a given problem A always follows from the computability of other given problems B1,...,Bn. Moreover, it provides a uniform way to actually construct a solution (algorithm) for such an A from any known solutions of B1,...,Bn.

CoL formulates computational problems in their most general—interactive—sense. CoL defines a computational problem as a game played by a machine against its environment. Such a problem is computable if there is a machine that wins the game against every possible behavior of the environment. Such a game-playing machine generalizes the Church–Turing thesis to the interactive level. The classical concept of truth turns out to be a special, zero-interactivity-degree case of computability. This makes classical logic a special fragment of CoL. Thus CoL is a conservative extension of classical logic. Computability logic is more expressive, constructive and computationally meaningful than classical logic. Besides classical logic, independence-friendly (IF) logic and certain proper extensions of linear logic and intuitionistic logic also turn out to be natural fragments of CoL. Hence meaningful concepts of "intuitionistic truth", "linear-logic truth" and "IF-logic truth" can be derived from the semantics of CoL.

CoL systematically answers the fundamental question of what can be computed and how; thus CoL has many applications, such as constructive applied theories, knowledge base systems, systems for planning and action. Out of these, only applications in constructive applied theories have been extensively explored so far: a series of CoL-based number theories, termed "clarithmetics", have been constructed as computationally and complexity-theoretically meaningful alternatives to the classical-logic-based first-order Peano arithmetic and its variations such as systems of bounded arithmetic.

Traditional proof systems such as natural deduction and sequent calculus are insufficient for axiomatizing nontrivial fragments of CoL. This has necessitated developing alternative, more general and flexible methods of proof, such as cirquent calculus.

Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).

Possible passages

Found by search and not yet checked by a person; they may only mention the idea in passing.

Any such select set is called the set of postulates, or premises, from which the reasoning proceeds. The reasoning is nothing else than the exhibition of the whole pattern of general conditions involved in the pattern derived from the selected postulates.
Alfred North Whitehead, Science and the modern world
States what Computability logic is.
Read the chapter · Open in the reader
Simplicity and objectivity do not have to be secured through elaborate and labored metaphysical construction. The data are simple and the hypothesis objective in so far as they accomplish the work where unto they are called--the removal of conflict, ambiguity, and inhibition in conduct and affection. In the experimental conception of inference it is clear that the principles of formal logic must play their role…
John Dewey, Creative Intelligence
States what Computability logic is.
Read the chapter · Open in the reader
(2) It follows from this that the 'reasonable' result, though it be only a thought and abstract, is still a concrete, being not a plain formal unity, but a unity of distinct propositions. Bare abstractions or formal thoughts are therefore no business of philosophy, which has to deal only with concrete thoughts. (3) The logic of mere Understanding is involved in Speculative logic, and can at will be elicited from it…
Georg Wilhelm Friedrich Hegel, The Logic of Hegel
Close in meaning to Computability logic; the term itself is not named.
Read the chapter · Open in the reader

Computability logic

Overview

Possible passages

Related ideas

Opposing perspectives

Place in the tradition