Скачать или смотреть Martin-Löf's Type Theory: Programming with Proofs

The source introduces Martin-Löf's type theory, a concept bridging pure mathematics and computer science by demonstrating a profound link between mathematical proofs and computer programs. It addresses the ambitious goal of creating bug-free software by proposing that a program's structure can guarantee its correctness, contrasting with traditional testing methods that only reveal existing errors. The core idea, known as the Curry-Howard isomorphism, posits that propositions in logic are equivalent to types in programming, meaning proving a theorem is akin to writing a program that "has" that theorem as its type. This is achieved through dependent types, which allow types to carry properties and verify correctness at compile time, virtually eliminating common bugs. The lecture highlights real-world proof assistants like Coq, Agda, and Isabelle/HOL that implement these principles, enabling the creation of provably correct software, and looks towards future advancements in the field such as homotopy type theory.

Glossary of Key Terms
Martin-Löf's Type Theory: A foundational system that integrates logic and computation by establishing a deep correspondence between propositions (in logic) and types (in programming), and between proofs and programs.
Bug-Free Dream: The ideal goal in computer science of creating software that is provably correct, where its structure inherently guarantees its absence of errors, rather than relying on testing to find their presence.
Curry-Howard Isomorphism: A fundamental principle stating a direct structural correspondence between formal logic and computer programming, where propositions are types and proofs are programs.
Proposition: In logic, a statement that can be either true or false.
Proof: In logic, a demonstration or argument establishing the truth of a proposition.
Type: In programming, a classification that dictates what kind of value a variable can hold or what kind of input a function expects and output it produces (e.g., integer, string).
Program: In computation, a set of instructions, or a value/function that inhabits a specific type.
Dependent Type: A type whose definition depends on a value or another type. It allows types to express properties and invariants of the data they classify, leading to greater precision and safety.
Out-of-Bounds Error: A common programming error where a program attempts to access an array element outside of its defined boundaries.
Off-by-One Bug: A common programming error involving iterative loops or arrays, where the calculation of an index or boundary is incorrect by one unit.
Buffer Overflow: A security vulnerability and common error where a program writes more data to a buffer than it can hold, overwriting adjacent memory locations.
Proof Assistant: A software tool that helps users write and verify mathematical proofs and formalize software. It checks the logical correctness of proofs/programs line by line.
Coq, Agda, Isabel/HOL: Examples of modern, widely used proof assistants built on the principles of type theory.
Automath: An early pioneer and one of the first systems designed for formalizing mathematics and checking proofs, influencing later type theory developments.
Homotopy Type Theory (HoTT): An advanced area of research that connects type theory to higher-dimensional geometry and topology, offering new ways to formalize mathematics and reasoning about complex structures.
Cubical Type Theory: A variant of type theory that provides a computational interpretation of higher-dimensional paths, offering an alternative foundation for univalent mathematics.
Univalent Foundations: A research program, often associated with Homotopy Type Theory, aiming to provide new foundations for mathematics where isomorphic structures are considered strictly equal.