Computability, complexity, and efficiency

Part 1 - Computability

A mathematical problem is computable, if it can be solved by a computer. Computable problems are also called solvable, decidable, and recursive. Earlier it was believed that all mathematical problems were solvable, but in the 1930’s G?del, Turing, and Church showed that there are problems which can’t be solved. In other words, these problems are undecidable. Mathematician David Hilbert strongly believed that all of mathematics could be precisely axiomatized. Once this was done, there would be an “effective procedure”, an algorithm that would take as input any precise mathematical statement, and after a finite number of steps, decide whether the statement was true or false. Hilbert was asking for a decision procedure for mathematics. To understand this better, we have to know about the notion of first-order logic.

First-order logic is a mathematical language in which most mathematical statements can be formulated. Every statement in first-order logic has a precise meaning in every appropriate logical structure, i.e., it is true or false in each such structure. Those statements that are true in every appropriate structure are called valid. Those statements that are true in some structures are called satisfiable. Hilbert called the validity problem for first-order logic, the “Entscheidungsproblem” (decision problem).

Before there were computers, various mathematicians from around the world invented precise, independent definitions of what it means to be computable. Alonzo Church defined the Lambda calculus, Kurt G?del defined Recursive functions, Stephen Kleene defined Formal systems, and Alan Turing defined Turing machines. All these models are equivalent. Anything computable in the lambda calculus is computable by a Turing machine and similarly for any other pairs of the above computational systems. After this was proved, Church believed that the intuitive notion of computable is identical to the above precise notions. This “Church-Turing Thesis” is widely accepted by mathematicians.

In 1931, G?del shocked the mathematical world by proving his Incompleteness Theorem. It states that, there is no complete and computable axiomatization of the first-order theory of the natural numbers. In other words, there is no reasonable list of axioms from which we can prove exactly all true statements of number theory. A few years later, Church and Turing independently proved that the entscheidungsproblem is unsolvable. Church did this by using the methods of G?del’s Incompleteness Theorem to show that the set of satisfiable formulas of first-order logic is not recursively enumerable, i.e., they cannot be systematically listed out by a function computable by the lambda calculus. Turing introduced his machines and proved the unsolvability of the halting problem. He obtained the unsolvability of the Entscheidungsproblem as a corollary.

The halting problem is an undecidable problem. We can prove that there is no algorithm that correctly determines whether an arbitrary program will eventually halt when running on an arbitrary input data. Not only are there undecidable problems, but there are many more undecidable problems compared to decidable problems. In fact, there are uncountably many undecidable problems, whereas there are only countably many decidable problems.

I hope that this article will help you understand the concept of computability and motivate you to explore the landscape further. In the next part, I will discuss the concept of (computational) complexity. Please feel free to give your comments.