Mathematics is a symbol of pure reason. A large part of science is based on mathematics and logic. In a sense, mathematics is the language of reason, and it is the most successful of all human inventions. However, as we are about to see, even mathematics has its own limitations.
This article is excerpted from "The Boundaries of Reason" Chapter 9 Obstacles to Mathematics, this book is available in the "Back to the Bookstore", and interested parties can click on the mini program to search for the title of the book to buy.
Written by | [US] Nousan · Yanovsky
Translator | Wang Chen
1 After writing this letter, it is time to defend love
Paris, May 29, 1832. A young man is writing a book. He had to write the long letter quickly, because there was a lot to write, and he knew he would die the next day.
The letter was a summary of his mathematical research, and he wanted to put it all on paper before it was too late. He pleaded with his friend at the end of his letter: "Seek their public opinion from Jacobian or Gauss [of the world-famous mathematicians], not for them to judge the truth of these theorems, but to evaluate their importance." I hope that in the future someone will be able to unravel this mess. ”
The next day, he participates in a duel to defend his love for a woman, and as he expected, he is mortally wounded. After being taken to a local hospital, he survived only one day. His last words are said to have been addressed to his brother: "Don't cry, Alfred! It took all my courage to die at the age of 20. The young man's name was Évariste Galois (1811-1832), · and his work would forever be an important part of modern mathematics.
What's in this letter? Hermann Weyl, one of the greatest mathematicians and physicists of the 20th century, · wrote: "This letter is perhaps the most important work of all human literature if the novelty and profundity of the information it contains." Weyl may have been a bit exaggerated in his assessment, but Galois's work did contain ideas that were crucial to modern mathematics and physics. What important theories can a 20-year-old say?
Galois was born in 1811, when the frenzied atmosphere after the France Revolution had not yet dissipated, which allowed Galois to live a short and tragic life. His father was once the mayor of a small city outside Paris before committing suicide over a bitter political dispute. Galois was a young man with a passion and a complex mind, and his upbringing was not easy. At a young age, he was so obsessed with mathematics that he neglected other aspects of his studies. He didn't get into France's most prestigious École Polytechnique, and ended up at a second-tier university, but the teachers didn't really discover his intelligence. Galois submitted two papers for publication, both of which were lost by the editor. Later he became involved in radical political groups, which led to his expulsion from school. It is unclear who is on the other side of this deadly duel, and the identity of the woman who caused the duel is unknown. What kind of work could the young genius accomplish if he hadn't died young in such a tragic way? The answer to this question is a matter of guesswork.
Galois's work was related to the solution of polynomial equations. Before understanding his contributions, we must first study some history. Consider this simple equation:
ax + b = 0
Such equations are called "linear" equations, and most middle school students know how to find x:
x = –b/a
A more complex "quadratic" equation is in the form of:
ax^2 + bx + c = 0
This method of solving equations was known in classical times, and to this day, high school students are still learning to use "quadratic formulas" to find solutions to quadratic equations. There are actually two solutions to a quadratic equation:
and
Note that these formulas use operations such as addition, subtraction, multiplication, division, finding squares and square roots, and so on. What about the "three" equation? It looks like this:
ax^3 + bx^2 + cx + d = 0
Is there a standard formula for solving such equations? In the 16th century, Gerolamo · Cardano pointed out that there were three solutions to this equation and gave quite complex formulas. These formulas use common operations, including finding square and cubic roots. Moving on, we can try to solve the "fourth" equation:
ax^4 + bx^3 + cx^2 + dx + e = 0
Lodovico Ferrari (1522-1565· and Niccolò Fontana Tartaglia (1499-1557·· Niccolò Fontana Tartaglia (1499-1557) discovered the solution of the quadratic equation. You must be curious to know if we will write down the four formulas corresponding to these four possible solutions. Rather than writing them down, these "quadratic formulas" use ordinary operations, including finding the square root, the cube root, and the fourth root. And what about the "fifth" equation? It is shown below:
ax^5 + bx^4 + cx^3 + dx^2 + ex + f = 0
Things get a lot more interesting here. Some people may think that there is a "five-order formula" consisting of addition, subtraction, multiplication, division, and from the square root to the fifth root. This is not right! No such formula exists. At the beginning of the 19th century, Paul · Paolo Ruffini (1765-1822) and Niels Henrik ·Abel (1802-1829) · Niels proved that there was no such universal formula using ordinary arithmetic and finding square roots. This means that for every fifth-order equation consisting of a, b, c, d, e, f, there will never be a simple solution formula. This is yet another clear example of the limitations of mathematics. In general, the problem is unsolvable. However, there are easily finding solutions to some fifth-order equations. For example, x5 – 1 = 0 has a solution of x = 1.
That's what Galois is all about. He was able to use the coefficients of a given fifth-order equation to determine whether the equation could be solved by ordinary operations. For this purpose, Galois introduced the concept of a group. A group is a mathematical structure modeled on the concept of symmetry. Galois pointed out how to relate a group to each equation. With the help of these symmetries he was able to determine whether a given fifth-order equation could be solved by ordinary operations. When his work on solving fifth-order equations was understood, it was immediately used in many other areas of mathematics and science.
This notion of describing symmetry involves a major revolution in modern mathematics, chemistry, and physics. A large part of modern mathematics and science is the study of different forms of symmetry, and therefore different types of groups. From this perspective, we can finally understand Weyl's judgment on the importance of the content of Galois's letters: modern mathematics and science make extensive use of the ideas introduced by Galois.
If we were to explain exactly how the Galois theory works, we would be confused. Suffice it to briefly introduce this theory to describe the symmetry of mathematical or physical systems in the first place. Once this symmetry is established, researchers need to ensure that this symmetry is maintained under different calculations or physical laws. The fact that a system cannot violate its own symmetry can be seen as a limitation on that system.
The unsolvable classical ruler drawing problems we see in Section 9.1 can be proved unsolvable using the Galois theory. Another issue that we haven't discussed yet is whether certain regular polygons can be constructed with rulers. Equilateral triangles and squares are constructible. What about regular pentagons? What about any regular n-side? The Galois theory tells us which regular n-sides can be constructed using a ruler and gauge. So if
n = 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, …, 257, … , 65 537, …
Then the corresponding regular n-sided shape is constructible. In contrast, if
n = 7, 9, 11, 13, 14, 18, 19, 21, 22, 23, 25, …
Then such a regular n-sided shape is unconstructable.
This limitation described by Galois theory is reflected in an interesting example, the classic children's game of backgammon. This famous puzzle game features 15 small squares mounted in a 4×4 grid. You can move one block at a time, and the goal is to have the blocks in order, as shown in the right half of Figure 9-6. However, some opening arrangements are not sequential. A simple swap of the positions of the squares numbered 14 and 15 will not result in an orderly arrangement, nor will it be possible to revert back to the original arrangement from the ordered arrangement.
In fact, there are a total of 15 factorial (15!) possible arrangements for these blocks. Exactly half of these patterns are called "even permutations" and the other half are called "odd permutations". There is a symmetry in the movement of the normal form of the square, which can only change from even to even, or from odd to odd. These phenomena reflect the symmetry of the system. In Figure 9-6, one arrangement is an even arrangement, while the other is an odd arrangement.
It is because of this fact that no matter how many moves we make within the limits of the rules, we cannot change one arrangement into another.
The impossibility related to Galois theory can also be seen on the Rubik's Cube. Take out a perfectly assembled Rubik's Cube and twist only one corner of it (although this is against the rules). Break it up and let a non-observant friend (a friend who hasn't read the book) try to put it back together. It's impossible to accomplish. A single twist makes it impossible to get back to its original shape, no matter how many steps it takes.
In conclusion, Galois's theory of equations points out the limitations inherent in the solution of equations for ordinary operations such as multiplication, division, multiplication, and finding the square root. Over the years, mathematicians have developed other techniques that use calculus and infinity methods to solve some of these problems. So the Galois theory proves that some problems cannot be solved in a particular way. Similarly, if you are allowed to measure the exact length with a ruler, then all regular n-sides can be constructed. For a game of backgammon, it is easy to solve the problem by simply taking out all the pieces and putting them back in the correct order. The Rubik's Cube problem can always be solved by cheating, that is, taking it apart piece by piece and putting it back together in order. These are simple moves that bypass the mathematical limitations described by Galois.
2 Judgment problems that computers can never solve
Let's say you get a job working under a construction contractor, helping clients design their dream kitchen. Everything was going well until the wife of a certain millionaire walked in and wanted to change the floor in the kitchen. She didn't want ordinary square bricks, but wanted to use round bricks in an ingenious way. You point out to her that round bricks won't work because they will leave gaps that can't be filled, as shown in Figure 9-7.
Is a regular pentagon suitable (see Figure 9-8)?
A regular pentagon is also not suitable, but you don't give up and propose to her to use a regular hexagon, as shown in Figure 9-9.
There are no gaps this time. Regular hexagon can be used to tile the floor. It can be seen that some shapes are suitable for seamless splicing, and some are not. Figure 9-10 illustrates two other stitching methods that use only one shape.
Obviously, there are many other shapes that can be stitched together seamlessly. The world-famous Netherlands painter M. M. C. Escher C. Escher, 1898-1972) made some wonderful etchings, and he stitched these strange shapes together without leaving a single gap.
Consider the weird shape called the Myers shape in Figure 9-11.
One might think that it is impossible for such a strangely shaped piece to cover the floor without leaving gaps. But it can do it exactly. As shown in Figure 9-12, there is no problem at all.
Most of the shapes we see are stitched in a way that makes the pattern repeat itself. This type of splicing is said to be cyclical. In periodic stitching, the same pattern appears again and again. However, some shapes have a splicing style that does not have a repeating pattern. This type of splicing is said to be aperiodic. Think of a rectangle with an aspect ratio of 2×1. This shape makes it easy to create periodic splicing.
However, we can also use this rectangle to create aperiodic splices. Putting two of these rectangles together results in a square that can be placed vertically or horizontally, as shown in Figure 9-13. Since any pattern can be created like this, it is easy to create aperiodic stitching.
We can also take a step further on the issue of aperiodic patterns. There are combinations of certain shapes, and when you use them to stitch together, the patterns they form are never cyclical. In other words, these shapes can only be stitched together in an aperiodic pattern. Therefore, these shapes are called aperiodic tiles. Roger · Penrose discovered two sets of such shapes, one of which was a "kite" and a "dart" and the other was called a diamond (see Figure 9-14).
These shapes come in different colors. When these shapes are spliced in such a way that the same colors are mated together, the resulting pattern is not cyclical. Figures 9-15 and 9-16 are examples of this aperiodic splicing.
Let's get back to the work of putting together kitchen tiles for others. It would be great if there was a way to feed a combination of different shapes into a computer and let it tell us if those shapes could fit together into a large floor without gaps (regardless of the edges). We call this task of accepting shapes and judging whether they are suitable for splicing as a tiling problem. Computers that can solve the stitching problem will answer "no" to circles and regular pentagons, and "yes" to squares, equilateral triangles, regular hexagons, Myers graphs, Penrose's "kites" and "darts", and Penrose's diamonds. Such a computer program will be of great help in your work.
It is a pity that such a computer program could not exist. In the mid-60s of the 20th century, Robert ·Berger proved that there was no computer program capable of solving the splicing problem.
He proves this by pointing out that the problem is harder than the downtime we saw in Chapter 6. The downtime question asks whether a computer program will eventually shut down or be stuck in an endless loop. As we can see, it is impossible for any computer to solve the downtime problem. Since the splicing problem is harder, it can't be solved by any computer either.
Specifically, any computational process can be converted into a set of shapes, and the shapes can be stitched together into a plane if and only if these computational processes never stop. In other words, these shapes can be spliced to the floor, which is equivalent to a computational process that goes into an endless loop. (We've seen this conversion process in Section 6.3.) Figure 9-17 can be used to visualize this process of transforming (or reducing to) one problem to another.
In this diagram, a program enters from the left and then transforms into a set of shapes. Suppose (incorrectly) there is a computer that can judge whether a set of shapes can form a seamless joint. Then we have a way to tell if a program is stuck in an endless loop or down. Since we already knew that there was no way to solve the downtime problem, we knew that there was no way to solve the stitching problem.
A decision problem that a computer can never solve, such as a splicing problem, is called an undecidable problem. While there are clear definitions and objectively existing answers to these questions, no computer can ever solve them.
It is worth emphasizing that our method of proving that the splice problem is undecidable is based on the fact that the downtime problem is undecidable.
Downtime issues can be judged to be contradictory.
Figure 9-17 illustrates:
Splicing problems can be determined, and shutdown problems can be determined.
Combining these two entailment derivations, we get the splicing problem that can determine the contradiction. Therefore, the splicing problem cannot be determined. Determining whether a particular set of shapes can be used to splice flooring is just one of many issues that are more difficult and therefore impossible to determine than downtime, and there are many, many more.
This article is reprinted with permission from the WeChat public account "Turing New Knowledge".
Special Reminder
1. Enter the "Boutique Column" at the bottom menu of the "Huipu" WeChat official account to view a series of popular science articles on different themes.
2. "Back to Park" provides the function of searching for articles by month. Follow the official account and reply to the four-digit year + month, such as "1903", to get the article index in March 2019, and so on.