When code becomes a mathematical proof of its own correctness

Science · Published 20 October 2026 Swipe more like this →

In short: Imagine a programming language where it is impossible to write a bug that crashes the system. By treating types not just as labels, but as values that can depend on other values, computer scientists have bridged the gap between software engineering and formal logic.

Dependent types are a sophisticated feature of type theory where a type's definition depends on a specific value. In standard programming, a variable might be an 'integer,' but in a dependently typed system, a variable could be 'an array of exactly length n.' This allows for much tighter constraints on what a program can actually do. For example, a dependent pair can link an array with its length in a way that the compiler can verify as mathematically sound.

This isn't just a technical convenience; it is rooted in the Curry–Howard correspondence. In 1934, Haskell Curry observed that types in lambda calculus mirrored axioms in propositional logic. This was later expanded by Howard and de Bruijn to include dependent types, which correspond to universal ("for all") and existential ("there exists") quantifiers in predicate logic. Essentially, this means that a program written in a dependently typed language like Agda, Lean, or Coq is simultaneously a formal proof of its own specification.

However, this power comes with a significant computational cost. Because types can depend on values, checking if two types are equal might require running a computation. If a type system allows arbitrary values, the compiler might have to decide if two different programs produce the exact same result to determine if they are compatible. This introduces a tension between expressivity and decidability, a core challenge in the design of the 'calculus of constructions,' the most expressive corner of Henk Barendregt's lambda cube.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

• What if your computer programs were actually mathematical proofs in disguise?
• Type theory began as Russell's fix for a paradox and now runs proof software
• Data types are the hidden rules that keep computer programs from falling apart.
• In model theory, a type acts as a blueprint for how mathematical elements behave.
• Why the logic of computer programming is rooted in the structure of abstract categories
• The royal lineage of Elizabeth II expanded to include fifteen great-grandchildren by her death.
• Why heavy boats float while tiny paper clips sink
• The zoologist who saw the world through a surrealist lens
• Why some objects sink while others float: the math of compactness
• The American art museum voted number one in the United States
• The MP who wrote his own invoices and signed them with a fake name
• Is the universe filled with a secret, invisible substance?

More in Physics · More in Science · Latest · A–Z · All topics