Turing’s diagonalization proof is a type of this game in which you go through an infinite list of possible algorithms and repeatedly ask, “Can this algorithm solve the problem that I want to prove is incomputable?” .
“It’s kind of the ‘endless question,'” Williams says.
To win the game, Turing had to create a problem for which the answer was no for all algorithms. This means identifying certain inputs that cause the first algorithm to output a wrong answer, other inputs that cause the second algorithm to fail, and so on. He found these special inputs using a trick similar to one recently used by Kurt Gödel. prove Self-referential claims such as “this proposition cannot be proven” cause problems with the foundations of mathematics.
The key insight was that every algorithm (or program) can be represented as a string of 0’s and 1’s. This means that an algorithm can take the code of another algorithm as input, as in the error-checking program example. In principle, the algorithm can also take its own code as input.
With this insight, we can define uncomputable problems such as those in Turing’s proofs. “Given an input string representing the code of an algorithm, it outputs 1 if the algorithm outputs 0 when the algorithm’s own code is the input, and 1 otherwise.” Otherwise, outputs 0. ” Every algorithm that tries to solve this problem produces a wrong output for at least one input, the input that corresponds to your own code. This means that no algorithm can solve this perverse problem.
What you can’t do with denial
Computer scientists had not yet completed diagonalization. In 1965, Julis Hartmanis and Richard Stearns modified Turing’s argument as follows: prove Not all computable problems are created equal, and some problems are inherently more difficult than others. The results launched the field of computational complexity theory, which studies the difficulty of computational problems.
However, complexity theory also revealed the limitations of Turing’s inverse method. 1975, Theodore Baker, John Gill, Robert Solovey proven Many unresolved problems in complexity theory can never be solved by diagonalization alone. The most important of these is the famous P versus NP problem. This problem asks whether all problems with easily checked solutions can be easily solved with a suitable creative algorithm.
Diagonalization’s blind spots are a direct result of the high level of abstraction that makes diagonalization so powerful. Turing’s proof did not involve any uncomputable problems that might arise in practice. Instead, they made up such problems on the spot. Other diagonalization proofs are similarly far removed from the real world and cannot solve problems where real world details are important.
“They handle the calculations remotely,” Williams said. “I imagine someone working with a virus and accessing it through their glove box.”
Failure of diagonalization means that to solve the P vs. NP problem, long journey. However, despite its limitations, diagonalization remains one of the important tools in the complexity theorist’s arsenal. In 2011, Williams used this, along with a number of other techniques, to prove This means that certain limited computational models cannot solve very difficult problems. This result was unknown to researchers for his 25 years. Although we are far from resolving P vs. NP, we still represented significant progress.
If you want to prove something is impossible, never underestimate the power of just saying no.
original story Reprinted with permission from Quanta Magazine, Editorially independent publication simmons foundation Its mission is to enhance the public’s understanding of science by covering research developments and trends in mathematics, physical sciences, and life sciences.
