Outer Limits of Reason (59 page)

One might think that there is no way such a strange tile can cover a floor without leaving gaps. But in fact it is perfectly legitimate. As
figure 9.12
shows, it can be done.

Most of the shapes that we have seen tile in a way that the patterns repeat themselves. Such tilings are called
periodic
. Within a periodic tiling the same patterns show up over and over. There are, however, certain shapes that have tilings that do not have a repeating pattern. Such tilings are called
nonperiodic.
Consider the simple 2-by-1 rectangle. It is very easy to make periodic tilings using this shape. However, we can also make nonperiodic tilings with the rectangle. Putting the rectangles together makes squares, which can be placed vertically or horizontally as in
figure 9.13
. Since any pattern can be made like this, it is easy to make nonperiodic patterns.
¹³

One can go further with nonperiodic patterns. There are certain sets of shapes that when you tile with them they are
never
periodic. In other words, the only patterns that can be made with these shapes are nonperiodic patterns. Such shapes are called
aperiodic tiles.
Roger Penrose discovered two such sets of shapes. One pair of shapes are “kites” and “darts” and the other pair are called rhombuses (see
figure 9.14
).

These shapes have different colors. When the shapes are matched up such that the colors match, the patterns formed will not be periodic. Figures
9.15
and
9.16
are examples of such nonperiodic tilings.

Let us go back to your job helping people tile their kitchen floors. It would be wonderful if there were some way of entering different sets of shapes into a computer that would be able to tell if those shapes are able to tile a large floor (don't worry about the ends) without gaps. We call this task of accepting shapes and determining if they are good for tiling the
Tiling Problem
. A computer that could solve the Tiling Problem would answer “No” to circles and pentagons, while answering “Yes” to squares, triangles, hexagons, Myers shape, Penrose's kite and dart, and Penrose's rhombuses. This computer program would be a tremendous help in your job.

Alas, no such computer program can ever exist! In the mid-1960s Robert Berger proved that no computer exists that can solve the Tiling Problem. He proved this by showing that this problem is harder than the Halting Problem, which we met in
chapter 6
. Remember that the Halting Problem asks whether a computer program will eventually halt or go into an infinite loop. As we saw, it is impossible for any computer to solve the Halting Problem. Since the Tiling Problem is even harder, it too cannot be solved by any computer.

In detail, one can transform any computational process into a set of shapes such that those shapes can tile any plane if and only if the computational process will never halt. That is, the fact that the shapes tile the room is equivalent to the computational process going into an infinite loop. (We saw such transformations in 
section 6.3
.) We might envision this transformation, or reduction, of one problem into another as in
figure 9.17
.

In the diagram, a program enters on the left and is then transformed into a set of shapes. Assume (wrongly) that there is a computer that can determine whether a set of shapes can be a good tiling. Then we would have a way of deciding if any program will go into an infinite loop or will halt. Since we already know that there is no possible way to solve the Halting Problem, we know that there is no possible way of deciding the Tiling Problem.

Decision problems like the Tiling Problem, which a computer can never solve, are called
undecidable problems
. Although these problems are clearly defined and have objective answers, there is no way any computer can ever solve them.

It is worth emphasizing that we showed that the Tiling Problem is undecidable by piggybacking on the fact that the Halting Problem is undecidable. In 
section 6.2
we showed that

The Halting Problem is decidable ⇒ contradiction.

Figure 9.17
shows that

The Tiling Problem is decidable ⇒ the Halting Problem is decidable.

Combining these implications tells us that

The Tiling Problem is decidable ⇒ contradiction

and hence the Tiling Problem is undecidable.

 

Deciding whether a specific set of shapes can tile a floor is only one of many problems that are harder than the Halting Problem and hence undecidable. There are many more such problems. I will examine two of them.

We saw in the last section that Ruffini and Abel proved that there is no general method for solving a polynomial equation with one variable that is to the fifth or higher power. Here is a related problem: given a polynomial equation with integer coefficients and any number of variables, determine if integer solutions to the equation exist. Equations where we only permit integer solutions are called
Diophantine equations
. Also, we are not looking for the solution to the equation. Rather, we are interested in an algorithm that will decide if an integer solution exists. The challenge to find such a procedure was one of the hard problems that David Hilbert presented to the mathematical world at the beginning of the twentieth century and that came to be known as
Hilbert's Tenth Problem
.

Some examples:

x
²
+
y
³
= 134

has a solution:
x
=
3 and
y
= 5. In contrast, it is easy to see that the equation

x
²
– 2 = 0

does not have an integer solution. What about a complicated equation like

x
⁴
y
³
z
⁷
– 23
x
⁵
y
²
+ 45
x
²
= 231?

Is there a solution? I simply do not know. It would be nice if there were a computer program that would solve Hilbert's Tenth Problem. Such a program would accept a Diophantine equation as input and reveal if any integer solutions exist.

In 1970, a twenty-three-year-old Russian mathematician named Yuri Matiyasevic—building on earlier work of Martin Davis, Hilary Putnam, and Julia Robinson—finally proved that no computer program that solves this problem can exist. That is, it is undecidable to tell if any given Diophantine equation has a solution.

Without getting into the nitty-gritty details of the proof, let us try to provide an intuition. Basically the mathematicians showed that for a given computation, one can devise a Diophantine equation such that the computation will halt if and only if the equation has integer solutions. In terms of 
figure 9.17
, the inner decider would be a Diophantine equation decider. If there were a mechanical way to decide if the Diophantine equation has a solution, then there would be a mechanical way to decide the halting problem. In other words, Hilbert's tenth problem is harder than the halting problem. Alas, no method exists to solve the halting problem and hence no method exists to solve Hilbert's tenth problem.

Another major problem shown to be undecidable is called the
word problem for groups
. Groups are mathematical structures that were first formulated by Galois, whom we met in the last section. These structures express symmetries and show up everywhere . . . including your bedroom. To get a feel for what groups are all about, let's step into the bedroom for a few minutes and meditate on a mattress. Proper care of a mattress demands that it be reoriented every few months. There are actually three basic ways of reorienting a mattress, as depicted in
figure 9.18
. A mattress can be flipped along its long edge (L), flipped along its short edge (S), or simply rotated (R).