Computability logic¶

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.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8616
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Mathematical Logic, Computability Theory → Mathematics

Core Idea¶

Computability logic is treated here as the recurring computer science and information systems identity summarized by this source-grounded definition: 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.

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 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.

For Computability logic, the abstraction is narrower than the article's general subject matter: a positive case must preserve 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. Retaining only the name, a familiar example, or a downstream effect is insufficient. The specialist roles and tests remain anchored in computer science and information systems, which is why this identity is domain-specific rather than prime.

How would you explain it like I'm…

Can-a-Computer-Do-It Logic

Most logic asks one question: is this true or false? Computability logic asks a different question: can a computer always actually get the job done? It is a way of doing logic about solving problems instead of about being true.

Logic About Solving, Not Truth

Logic is the study of good reasoning. Ordinary (classical) logic is about truth: its sentences are true or false, and an argument is valid when true starting sentences always lead to a true conclusion. Computability logic, started by Giorgi Japaridze in 2003, rebuilds logic around a different question — what can be computed. In computability logic, something counts as valid when it is always computable, meaning a machine can always successfully handle it.

Logic of Computability

Computability logic (CoL) is a research program and mathematical framework, introduced and named by Giorgi Japaridze in 2003, that rebuilds logic as a formal theory of computability rather than of truth. In classical logic, formulas stand for true-or-false statements, and validity depends only on an argument's form: it tells you when the truth of some statements always follows from the truth of others. CoL keeps the idea of a systematic logic but changes what validity means: a formula is valid when it is always computable. So instead of asking whether truth is preserved, CoL asks whether computability is guaranteed. This makes it a logic about what machines can reliably do, not just about what is so.

Computability logic (CoL) is a research program and mathematical framework, introduced and so named by Giorgi Japaridze in 2003, that redevelops logic as a systematic formal theory of computability, in contrast with classical logic as a formal theory of truth. In classical logic, formulas represent true/false statements, validity is a matter of form alone, and the logic characterizes when the truth of a statement always follows from the truth of a set of premises. CoL reinterprets the central notion of the discipline: validity means being always computable. The program is thus a wholesale reconstruction of logic around computational rather than truth-theoretic semantics, not merely an application of logic to computing. What makes something an instance of CoL is this foundational replacement of truth by computability as the organizing concept; sharing vocabulary with computation or simply studying algorithms is not enough. It sits at the boundary of mathematics and computer science, and its methods and tests are anchored there.

Structural Signature¶

Sig role-phrases:

Defining carrier — Elementary atoms, which are nothing but the atoms of classical logic, represent elementary problems, i.e., games with no moves that are automatically won by the machine when true and lost when false.
Constitutive relation — Both semantically and syntactically, classical logic is nothing but the fragment of CoL obtained by forbidding general atoms in its language, and forbidding all operators other than ¬, ∧, ∨, →, ∀, ∃.
Operating condition — Each run (play) is won by one of these players and lost by the other.
Recognition evidence — The operation ¬ of negation ("not") switches the roles of the two players, turning moves and wins by the machine into those by the environment, and vice versa.
Admissible variation — Such a game can be easily won regardless who the adversary is, by copying his moves from one board to the other.
Characteristic consequence — The parallel implication operator → ("pimplication") is defined by A→B = ¬A∨B.
Failure boundary — The parallel quantifiers ∧ ("pall") and ∨ ("pexists") can be defined by ∧ xA(x) = A(0)∧A(1)∧A(2)∧... and ∨ xA(x) = A(0)∨A(1)∨A(2)∨....

What It Is Not¶

Not the whole field of computer science and information systems. The node requires the specific identity stated by 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.
Not an over-broad reading. At any time, however, the environment is allowed to make a "replicative" move, which creates two copies of the then-current position of A, thus splitting the play into two parallel threads with a common past but possibly different future developments.
Not an over-broad reading. Their notable distinguishing feature from other approaches with similar aspirations (such as bounded arithmetic) is that they extend rather than weaken PA, preserving the full deductive power and convenience of the latter.
Not an over-broad reading. However, static games never punishes a player for "thinking" too long (delaying its own moves), so such games never become contests of speed.
Not automatically Entscheidungsproblem. Retrieval proximity does not establish equivalence; the two identities must be compared by carrier, operation, and failure boundary.

Scope of Application¶

Computability logic applies literally inside computer science and information systems wherever the source-defined carrier and relation can be established. Its documented habitats include:

As a problem solving tool. It typically includes all Peano axioms, and adds to them one or two extra-Peano axioms such as ⊓ x ⊔ y(y=x) expressing the computability of the successor function.
As a problem solving tool. So, such a theory can be used for finding not merely algorithmic solutions, but also efficient ones on demand, such as solutions that run in polynomial time or logarithmic space.
Documented setting. 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.
Documented setting. This has necessitated developing alternative, more general and flexible methods of proof, such as cirquent calculus.
Documented setting. 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.
Language. The full language of CoL extends the language of classical first-order logic.

Outside computer science and information systems, the name should be retained only when these same operational conditions survive; otherwise the comparison belongs to the broader parent Pattern or should be marked as analogy.

Clarity¶

A clear use of Computability logic names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is 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. The strongest recognition evidence in the frozen account is: The operation ¬ of negation ("not") switches the roles of the two players, turning moves and wins by the machine into those by the environment, and vice versa. A report should distinguish that evidence from a proxy, consequence, or common implementation. It should also state the qualification At any time, however, the environment is allowed to make a "replicative" move, which creates two copies of the then-current position of A, thus splitting the play into two parallel threads with a common past but possibly different future developments. so that a reader can reproduce the classification rather than infer it from topical resemblance.

Manages Complexity¶

Computability logic compresses multiple computer science and information systems details into a stable diagnostic relation. The source shows both the central mechanism—both semantically and syntactically, classical logic is nothing but the fragment of CoL obtained by forbidding general atoms in its language, and forbidding all operators other than ¬, ∧, ∨, →, ∀, ∃.—and the practical consequence—the parallel implication operator → ("pimplication") is defined by A→B = ¬A∨B. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit. It is lossy by design: local history and implementation details may be omitted only when they do not alter the defining relation.

Abstract Reasoning¶

Type the carrier. Identify the computer science and information systems entities to which the claim applies.
State the relation. Use the source-grounded identity: 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.
Check operation and conditions. Each run (play) is won by one of these players and lost by the other.
Demand recognition evidence. The operation ¬ of negation ("not") switches the roles of the two players, turning moves and wins by the machine into those by the environment, and vice versa.
Test variation. Change an implementation or setting while preserving such a game can be easily won regardless who the adversary is, by copying his moves from one board to the other.
Run the collapse test. Remove the defining operation; if the label still seems equally apt, only a topic or correlate was retained.
Reduce cautiously. When the specialist conditions cannot be carried, route the residual comparison to Pattern.

Knowledge Transfer¶

Within the home domain. Knowledge about Computability logic transfers literally when a new case preserves the same carrier type, relation, and recognition test. It typically includes all Peano axioms, and adds to them one or two extra-Peano axioms such as ⊓ x ⊔ y(y=x) expressing the computability of the successor function. So, such a theory can be used for finding not merely algorithmic solutions, but also efficient ones on demand, such as solutions that run in polynomial time or logarithmic space.

Beyond the home domain. No canonical parent is asserted for Computability logic. An outside case receives the specialist name only when the same typed roles and rejection conditions can be filled literally; otherwise the comparison remains an analogy pending later graph densification.

Examples¶

Canonical¶

Their notable distinguishing feature from other approaches with similar aspirations (such as bounded arithmetic) is that they extend rather than weaken PA, preserving the full deductive power and convenience of the latter. This case is canonical because it supplies a concrete carrier and lets the defining relation be checked rather than merely named.

Mapped back: carrier → the entities in the documented case; operation → 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; recognition evidence → The operation ¬ of negation ("not") switches the roles of the two players, turning moves and wins by the machine into those by the environment, and vice versa

Applied / In Practice¶

Due to the expressiveness of this language, advances in CoL, such as constructing axiomatizations or building CoL-based applied theories, have usually been limited to one or another proper fragment of the language. The applied case shows how the identity is used under a second setting or qualification while keeping the same operative relation.

Mapped back: changed setting → Language; invariant → 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; boundary → the case exits the class when at any time, however, the environment is allowed to make a "replicative" move, which creates two copies of the then-current position of A, thus splitting the play into two parallel threads with a common past but possibly different future developments

Structural Tensions¶

T1 — Stable identity versus admissible variation. At any time, however, the environment is allowed to make a "replicative" move, which creates two copies of the then-current position of A, thus splitting the play into two parallel threads with a common past but possibly different future developments. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Which changes preserve the defining relation, and which replace it?

T2 — Recognition versus proxy. Their notable distinguishing feature from other approaches with similar aspirations (such as bounded arithmetic) is that they extend rather than weaken PA, preserving the full deductive power and convenience of the latter. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the cited evidence establish the identity or only a correlated sign?

T3 — Definition versus implementation. However, static games never punishes a player for "thinking" too long (delaying its own moves), so such games never become contests of speed. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Is the observed implementation constitutive, optional, or merely common?

T4 — Scope versus overextension. When such operators are applied to non-elementary games, however, their behavior is no longer classical. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Can every claimed application fill the same typed roles without metaphor?

T5 — Transfer versus domain accent. Elementary atoms, which are nothing but the atoms of classical logic, represent elementary problems, i.e., games with no moves that are automatically won by the machine when true and lost when false. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the receiving case instantiate Computability logic literally, co-instantiate Pattern, or only resemble it?

T6 — Autonomy versus reduction. Both semantically and syntactically, classical logic is nothing but the fragment of CoL obtained by forbidding general atoms in its language, and forbidding all operators other than ¬, ∧, ∨, →, ∀, ∃. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: What does Computability logic distinguish that the broader parent Pattern leaves together?

Structural–Framed Character¶

Computability logic is structural-leaning. Its structural side is the repeatable organization summarized by 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. Its framed side is the computer science and information systems vocabulary that fixes the carrier, evidence, exceptions, and admissible transformations.

Evaluative weight: the identity can be stated descriptively even when applications carry practical stakes. Human-practice dependence: the source-grounded carrier determines whether the relation exists independently or is constituted by a practice. Institutional origin: disciplinary conventions stabilize the name and test. Vocabulary portability: Each run (play) is won by one of these players and lost by the other. Import versus recognition: literal transfer requires the same mechanism; shape alone is analogy.

Its portable skeleton is Pattern. Its character: a recurring specialist identity whose thin organization can be abstracted, while its operational meaning remains domain-bound.

Structural Core vs. Domain Accent¶

What is skeletal. 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. The stable skeleton is the typed relation expressed in that definition and the entry's recognition and collapse tests. The source identifies these operative conditions: Elementary atoms, which are nothing but the atoms of classical logic, represent elementary problems, i.e., games with no moves that are automatically won by the machine when true and lost when false. Both semantically and syntactically, classical logic is nothing but the fragment of CoL obtained by forbidding general atoms in its language, and forbidding all operators other than ¬, ∧, ∨, →, ∀, ∃. It further constrains recognition and variation through: Each run (play) is won by one of these players and lost by the other. The operation ¬ of negation ("not") switches the roles of the two players, turning moves and wins by the machine into those by the environment, and vice versa.

What is domain-bound. computer science and information systems supplies the operative entities, technical vocabulary, warrants, and exceptions that make Computability logic literal. Its documented scope includes the condition that It typically includes all Peano axioms, and adds to them one or two extra-Peano axioms such as ⊓ x ⊔ y(y=x) expressing the computability of the successor function. Another bounded application condition is that So, such a theory can be used for finding not merely algorithmic solutions, but also efficient ones on demand, such as solutions that run in polynomial time or logarithmic space. These are not decorative examples; they determine which carrier and evidence can fill the abstraction's roles.

Why no parent is asserted. Removing those specialist details does not currently yield one live catalog node that is a necessary genus for every instance. The entry is therefore approved as unparented rather than attached by topical resemblance. Its collapse evidence remains specific—Such a game can be easily won regardless who the adversary is, by copying his moves from one board to the other.—and future graph densification may discover a defensible relation only if it preserves that boundary.

Approved unparented node. No current live node supplies a defensible necessary genus or structural prerequisite for Computability logic. The reviewed identity is: 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. The accelerated suggestion was declined because topical or lexical similarity does not establish hierarchy; the node is admitted without a parent pending later graph densification.
Related reasoning operations. Evidence, representation, comparison, classification, transformation, or evaluation may participate in particular cases, but participation does not make any one of them a necessary parent of every instance.

Neighborhood in Abstraction Space¶

Computability logic sits in a moderately populated region (40^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Formal Logic & Semantic Systems (18 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Pattern. The parent omits the specialist differentia. Tell: Can the case establish 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?
Entscheidungsproblem. The historical decision problem asking for an algorithm that determines whether any first-order logical sentence is valid, proved impossible by Church and Turing. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Computability. The in-principle boundary between problems an effective procedure can solve and those none can. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Well-Formed Formula. In mathematical logic, propositional logic, and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet, constructed following the defined grammar of a formal language. Tell: Which entry's carrier, operation, and failure condition are satisfied?
A measurement, proxy, or consequence. Those may provide evidence without being the identity. Tell: Would Computability logic remain present if the detector or downstream effect changed?
A metaphorical analogue. A similar shape outside computer science and information systems lacks the specialist mechanism. Tell: Do the native roles transfer literally, or only the parent Pattern?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Computability_logic (revision 1311769599).
Preserved source candidate: https://arxiv.org/abs/cs/0507045
Preserved source candidate: https://arxiv.org/abs/1003.4719
Preserved source candidate: https://lmcs.episciences.org/2020/pdf
Preserved source candidate: https://arxiv.org/abs/math/0506553
Preserved source candidate: https://arxiv.org/abs/1105.3853
Preserved source candidate: http://www.csc.villanova.edu/~japaridz/CL/
Preserved source candidate: https://web.archive.org/web/20190419120954/http://www.csc.villanova.edu/~japaridz/
Preserved source candidate: https://web.archive.org/web/20160303174250/http://www.csc.villanova.edu/~japaridz/CL/gsoll.html

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.