Leonid A. Levin's Contribution to Complexity Theory

Title: Leonid A. Levin's Contribution to Complexity Theory

Abstract: Leonid A. Levin is a renowned mathematician and computer scientist known for his groundbreaking work in complexity theory. His research focuses on the boundaries between what is computable and what is not, and how these boundaries relate to the foundations of mathematics and logic. In his work, he has developed new techniques and ideas that have had a significant impact on the field.

Main Research Question: Can the formal system of Peano Arithmetic (PA) be consistently extended to a complete theory?

Methodology: Levin uses a combination of mathematical logic, computer science, and information theory to explore this question. He introduces the concept of mutual information, a measure of the amount of information that two sequences share. This concept is used to prove a "robust" version of the Godel Theorem, which states that there is a limit to what can be known within a formal system like PA.

Key Findings:

1. Levin shows that there is a gap between the usual interpretations of the Godel Theorem and what is actually proven. This gap involves complexity theory and the concept of mutual information. 2. He demonstrates that there are r.e. (recursively enumerable) sets of axioms that can be used to consistently extend PA, contrary to the common belief that such extensions are not possible. 3. Levin also applies his techniques to the problem of tiling, a task in computer science and mathematics where one tries to cover a surface with a specific pattern. He shows that there are palettes of tiles that can be used to tile an infinite plane, but only non-recursively.

Significance: Levin's work has significant implications for the field of complexity theory and the foundations of mathematics and logic. His techniques and ideas have opened up new avenues of research and have challenged existing assumptions about the limits of computability. His work on the Godel Theorem has provided a new perspective on this classic result, and his applications to tiling have expanded the scope of complexity theory.

Link to Article: https://arxiv.org/abs/0203029v2 Authors: arXiv ID: 0203029v2