The limits of knowledge | Mathematics - Medium

Gödel, Turing, and the science of what we can and cannot know by Samuel Flender, Applied Scientist at Amazon, published in Towards Data Science.

Kurt Gödel (left) and AlanTuring (right) 
Photo: Cantor’s Paradise

In the seventeenth century, German mathematician Gottfried Leibnitz proposed a machine that could read any mathematical statement as input and determine whether it is true or false, based on the axioms of Mathematics. But is every statement decidable like that? Or are the limits to what we can know? This question has become known as the Entscheidungsproblem (decision problem).

Two centuries later, another German mathematician, David Hilbert, declared optimistically that the answer to the Entscheidungsproblem had to be, yes, we can and will know the answer to any mathematical question. In an address in 1930 in German town Königsberg he famously said,

Wir müssen wissen — wir werden wissen. (‘We must know — we will know.’)

But will we?

The limits of Mathematics

Hilbert’s optimism turned out to be short-lived. In the same year, Austrian Mathematician Kurt Gödel demonstrated that there are limits to our knowledge in Mathematics by proving his famous incompleteness theorem...

The limits of computation

Alan Turing was a graduate student at Cambridge University when he first learned about Gödel’s incompleteness theorem. During that time, Turing was working on formulating the mathematical design of machines that could process any input and compute a result, similar to what Leibnitz had envisioned centuries earlier. These conceptualized machines are today known as Turing machines, and turned out to be the blueprint for the modern digital computer. In simple terms, a Turing machine can be likened to a modern computer program...

While Gödel proved that Mathematics is incomplete, Turing proved that Computer Science is in some sense ‘incomplete’, too. Certain programs simply cannot exist. This is not just a theoretical curiosity: the halting problem has many practical implications in Computer Science today. For instance, if we want a compiler to find the fastest possible machine code for a given program, we are actually trying to solve the halting problem — and we already know that the problem is not solvable.

Practical limits of knowledge: the P vs NP problem

By showing that there are problems that are fundamentally not solvable, Gödel and Turing demonstrated that there are theoretical limits to what we can ever know. But in addition, there are other problems that we could solve in theory, but not in practice because it simply takes too long to compute the solution.

Read more... 

Source: Medium