Revisit Turing's principle and feel the power of proof by contradiction

Algorithms have become ubiquitous, and it seems that for every problem that can be expressed in precise mathematical terms, there is a corresponding algorithm. However, this is not the case. In fact, some seemingly simple problems can never be solved by algorithms. Alan Turing, a pioneer among computer scientists, proved this in a paper nearly a century ago. Because of the existence of such "uncomputable" problems, he proposed the computational mathematical model that launched modern computer science.

Turing demonstrated this groundbreaking result using a counterintuitive strategy: He defined a problem that resisted all attempts to solve it. "For example, if I ask you what you are doing, no matter what your answer is, I will say, 'What I am going to do is different from what you said,'" said Rahul Ilango, a graduate student at MIT studying theoretical computer science. Rewritten content: Turing demonstrated this groundbreaking result with a counterintuitive strategy: he defined a problem that resisted all attempts to solve it. "For example, if I ask you what you are doing, no matter what your answer is, I will say, 'What I am going to do is different from what you said.'" said Rahul Ilango, a graduate student at MIT studying theoretical computer science

Turing's strategy is based on a long-standing mathematical method called the "diagonal proof." The following is a simplified explanation of the logic behind his proof

String

The diagonal proof comes from a clever trick to solve a problem about strings. The value of each bit can be 0 or 1. The description of the problem is: Given a list of strings, all strings in the list are the same length, how can you generate a new string that is not in the list?

Rewritten content: One of the most straightforward strategies is to consider every possible string in order. Suppose there are five strings, each with five bits. First iterate over to check if 00000 exists in the list. If it doesn't exist, the problem is solved; if it exists, go to 00001 and repeat the process. This method is simple, but slow for long lists resulting from long strings

Diagonal turns out to be a viable alternative for incrementally building non-existent strings. Starting with the first bit of the first string in the list, reverse it and this will become the first bit of the new string. Then reverse the second bit of the second string and use it as the second bit of the new string, repeat this until you reach the end of the list. By reversing the bit operations, you ensure that the new string is different from every string in the original list by at least one position. (They also form a diagonal line in the list of strings, so it is called a diagonal proof.)

The diagonal proof simply requires checking each item in the list in turn. one bit in a string, so it's usually much faster than other methods, but its real power lies in how well it handles infinitely long string problems.

Ryan Williams, a theoretical computer scientist at MIT, said: "Although strings and lists can be infinite, the diagonalization method is still effective."

George Cantor Erl was the first to harness this power and was the founder of the mathematical field of set theory. In 1873, he used diagonals to show that some infinite values ​​are larger than others. Sixty years later, Turing applied this version of the diagonal proof to the theory of computation

Restrictions of Algorithms

In order to prove that there is a class of mathematical problems that are impossible Solved by any algorithm, Turing proposed a theory. This type of problem has well-defined inputs and outputs, but no defined process to convert the inputs into outputs. Turing focused primarily on decision-making problems and sought to better concretize this nebulous task. In a decision problem, the input can be any string consisting of 0 and 1, and the output can be 0 or 1

Determining whether a number is prime (divisible only by 1 and itself) is a decision An example of the problem - given an input string representing a number, the correct output is 1 if the number is prime and 0 if it is not prime. Another example is checking computer programs for syntax errors. The input strings represent code for different programs - all programs can be represented this way because that's how they are stored and executed on the computer - the rule is that if the code contains a syntax error, output 1, if not, Then output 0.

Only if an algorithm produces the correct output for every possible input, it can be said to solve the problem - if it fails even once, it is not a general algorithm for solving the problem. Typically, one specifies a problem that one wants to solve and then tries to find an algorithm to solve it. Turing turned this logic on its head when looking for unsolvable problems - he imagined an infinite list of all possible algorithms and used diagonalization to construct a puzzle that was opposed to every algorithm on the list .

Please imagine a new question consisting of 20 questions. Instead of starting from a specific concept, the answerer comes up with an example of dissatisfaction for each question in turn. When the game is over, the answerer has described a proposition consisting entirely of opposites of the question

Turing's diagonal proof process is to perform each algorithm in an infinitely long list of algorithms. Thinking: "Can this algorithm solve the problem we want to prove to be uncomputable?", like a game competition. Williams said: "This method transforms the original problem into an 'infinite problem.'"

To win the game, Turing needs to design a question in which the answer given by each algorithm is no. of. This means finding the specific input that made the first algorithm output the wrong answer, another input that made the second algorithm fail, and so on. He found that these special inputs used a method similar to that used by Kurt Gödel not long ago when he showed that self-referential assertions like "This proposition is not provable" can cause trouble in the foundation of mathematics. skills.

The key here is that every algorithm (or program) can be represented as a string of 0s and 1s. This means that, just like in the error checker example, an algorithm can take as input the encoding of another algorithm. In principle, the algorithm could even take its own encoding as input.

In this way, we can define a non-computable problem, just like the problem mentioned in Turing's proof: "Given an input string representing the code of an algorithm, when the code of the algorithm itself As input, if the algorithm outputs 0, let it output 1, otherwise it outputs 0." Every algorithm that attempts to solve this problem will produce incorrect output on at least one input, namely the input that corresponds to its own code. This means that this anomalous problem cannot be solved by any algorithm

What cannot be proved is proof by contradiction

The use of diagonal proofs by computer scientists does not end here. Finish. In 1965, Juris Hartmanis and Richard Stearns adapted Turing's argument to show that not all computable problems are equal—some are inherently more difficult than others. This result launched the field of computational complexity theory, the study of the difficulty of computational problems.

The development of complexity theory reveals the limitations of Turing's diagonal proof. In 1975, Baker, Gill, and Solovy showed that many unsolved problems in complexity theory could not be solved by diagonalization alone. The most important of them is the famous P/NP problem, which is simply a question about whether the correctness of the solution can be verified in polynomial time and whether it can be solved in polynomial time

Diagonal proof The limitations of are a direct result of the high level of abstraction that makes it so powerful. Turing's proof did not address any of the non-computable problems that might arise in practice - instead, problems tend to be abstract. Other diagonals prove equally far removed from the real world, so they cannot solve real-world problems.

Williams said: "The diagonal proof does not directly touch the problem itself, just like doing an experiment with a glove box."

The declining trend of the diagonal proof shows that solving P The /NP problem is going to be a long journey. Despite its limitations, diagonal proofs remain one of the key tools in the complexity theorist's arsenal. In 2011, Williams combined it with a range of other techniques to demonstrate that a restricted computational model was incapable of solving some incredibly difficult problems—a result that solved a problem that had vexed researchers for 25 years. While this is far from solving the P/NP problem, it still represents significant progress.

If you want to prove something is impossible, don’t underestimate the power of denial

Original link:

Needs rewriting The content is: https://www.quantamagazine.org/alan-turing-and-the-power-of-negative-thinking-20230905/

The above is the detailed content of Revisit Turing's principle and feel the power of proof by contradiction. For more information, please follow other related articles on the PHP Chinese website!