• The limits of knowledge
  • By Samuel Flender
  • The Nuggets translation Project
  • Permanent link to this article: github.com/xitu/gold-m…
  • Translator: Roc, LSvih
  • Proofreader: zhengjian-l, PingHGao

A story about Godel, Turing, and the science of what we can and cannot know

In the 17th century, The German mathematician Gottfried Leibnitz came up with a machine that could read any mathematical statement and determine whether it was true based on mathematical axioms. But can every statement be judged this way? Or is there a limit to what we can know? This problem is called the Entscheidungsproblem.

Two centuries later, another German mathematician, David Hilbert, optimistically declared that the answer to the deterministic problem must be that, yes, we can and will know the answer to any mathematical problem. In a 1930 speech in Konigsberg, Germany, he said:

Wir Mussen Wissen — Wir Werden Wissen. (” We must know — we will know.” )

But will we ever know?

The limits of mathematics

History suggests that Hilbert’s optimism was short-lived. That same year, the Austrian mathematician Kurt Godel showed that our mathematical knowledge has limits by proving his famous incompleteness theorem.

Here’s a simple way to understand Godel’s theorem. Please consider the following statement.

Statement S: This statement is unprovable.

Now, suppose that in mathematics we can prove that S is true. But then proposition S itself would be false and therefore inconsistent. Ok, so let’s assume the opposite, that we can’t prove S in mathematics. But that would mean that S itself is true, and that mathematics contains at least one true statement that cannot be proved to be true. Therefore, mathematics is either inconsistent or incomplete. If we assume that it is consistent (propositions cannot be both true and false), this can only lead to the conclusion that mathematics is incomplete, that there are true propositions that cannot be fully proved to be true.

Godel’s mathematical proof of the incompleteness theorem was much more complex than I outline here, radically changing Hilbert’s claim that complete knowledge was feasible (” We will know “). In other words, if we assume that mathematics is consistent, then we are bound to find unprovable true propositions.

For example, The Goldbach conjecture, according to which every even number is The sum of two primes:

6 is 3 plus 3, 8 is 3 plus 5, 10 is 3 plus 7, 12 is 7 plus 5, and so on.

No one has yet found a counterexample, and if the conjecture is true, there is no counterexample. Thanks to Godel’s contribution, we know that there are unprovable true propositions, but unfortunately we have no way of finding them. Goldbach’s conjecture could be one of them, and if so, it would be a waste of time trying to prove it.

Kurt Godel (left) and Alan Turing (right)

Limit of calculation

Alan Turing first learned about Godel’s incompleteness theorem as a graduate student at Cambridge university. During that time Alan was busy working on a mathematical design for a machine. The machine can process any input and compute the result, similar to what Leibniz envisioned centuries ago. Today these conceptualized machines are known as Turing machines and are the blueprint for modern digital computers. Simply put, a Turing machine can be thought of as a modern computer program.

Alan was working on the so-called downtime problem, which can be described as follows:

Is there a program that can determine whether another program will stop (stop) or not stop (loop)?

Alan proved that the answer to the shutdown question was’ no ‘, that there was no such procedure. Like Godel’s work, he is demonstrating with “proof by objection”. Suppose there is a program, halts(), that determines whether a given program will stop. However, we can also build the following programs:

def g() :
    if halts(g):
        loop_forever()
    return
Copy the code

See what’s happening here? If g is true, then g is not true; If g is not true, then g is true. Either way, we’re going to get a contradiction. Therefore, the program halts() does not exist.

Godel had shown that mathematics was incomplete, and Alan had shown that computer science was in a sense ‘incomplete’. Some programs simply don’t exist. This is not just a theoretical curiosity: the outage problem has many practical implications in computer science today. For example, if we want the compiler to find the fastest machine code for a given program, we are actually trying to solve an outage problem that we already know is unsolvable.

A Complex Protein Structure — Predicting how proteins fold is an NP-Problem

Practical limits of knowledge: P vs. NP problems

Godel and Alan proved that there was a theoretical limit to what we could know by revealing the existence of problems that were fundamentally unsolvable. But in addition, there are other problems that we can solve in theory, but we can’t actually solve because it takes too long to solve. Here we will show the difference between P and NP problems.

P problems are problems that can be solved in a “reasonable amount of time”. Here, “reasonable time” means “polynomial time” (hence the name P). The computational complexity of solving these problems increases exponentially with the size of the problem input (think multiplication or sorting problems).

On the other hand, NP problems are problems that cannot be solved in a reasonable amount of time. NP is the Abbreviation of non-deterministic polynomial. It means that a solution of a problem can be verified with polynomial computational complexity, but it cannot be solved with polynomial computational complexity. The complexity of solving NP problems is exponential, not polynomial, which makes a huge practical difference. Examples of NP problems include optimal scheduling, predicting how proteins fold, encrypting messages, solving sudoku puzzles, optimal packaging (also known as the knapsack problem) or optimal routing (also known as the traveling salesman problem). Some problems (such as finding the discrete Fourier transform of a function) started out as NP problems, but eventually became P problems as new and clever algorithms were developed to simplify the solution.

One of the great unsolved mysteries in computer science today is the P vs. NP question: does P equal NP? In other words, for all the problems where we can verify a solution in a reasonable amount of time, can we solve it in a reasonable amount of time?

The P and NP problems are so important that they were included in the Millennium Prize Problems. If you find the answer, you’ll win a million dollars. It is hard to overstate the importance of this issue: a world where P=NP is fundamentally different from a world where P≠NP. If P=NP, then we can say for sure that there is a faster way to solve sudoku puzzles, or predict how proteins fold, and we just haven’t found it yet. There’s no doubt that understanding how proteins fold could have real-world implications for everything from understanding the pathology of Alzheimer’s disease to curing cancer.

Today, most scientists believe that P does not equal NP, but can we be sure? The P and NP problem itself may resemble Hilbert’s Entscheidungs problem or Turing’s downtime problem: it may have no answer at all.

References and further reading

  • Complicated by Melanie Mitchell
  • P vs NP and complexity in zoos (Video)
  • Godel’s incompleteness theorem (video)

If you enjoyed this article, you can also check out the following:

  • How to Reduce errors — a Bayesian guide to Predicting the future with limited Data
  • Haphazard trajectory-random walks through physics, finance and our lives

If you find any mistakes in your translation or other areas that need to be improved, you are welcome to the Nuggets Translation Program to revise and PR your translation, and you can also get the corresponding reward points. The permanent link to this article at the beginning of this article is the MarkDown link to this article on GitHub.

The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. The content covers Android, iOS, front-end, back-end, blockchain, products, design, artificial intelligence and other fields. If you want to see more high-quality translation, please continue to pay attention to the Translation plan of Digging Gold, the official Weibo, Zhihu column.