Once Upon an Algorithm Read online

  It might seem odd to give an algorithm its own description as input, but this is not really such a strange idea. For example, Loop(Loop), that is, Loop applied to itself, would not terminate because Loop only terminates for the input 1. What happens if we apply Halts to itself? Would Halts(Halts) terminate? Yes, since Halts by assumption says for any algorithm, whether or not it halts, it has to terminate to do this; so it should terminate specifically when applied to itself.

  The rationale for the definition of Selfie becomes clear when we consider what happens when we execute the algorithm Selfie with itself given as input. This, in fact, leads to a paradoxical situation that calls into question the possibility of Halts’s existence. We can get a glimpse of what’s going on by unfolding the definition of Selfie when applied to itself. To do so, we substitute Selfie for the parameter Alg in its definition. As shown in the middle graphic of figure 11.4, this leads to a loop that terminates when Selfie applied to its own definition does not halt, because if Halts(Selfie,Selfie) is true, the algorithm loops back to test the condition again, and otherwise stops.

  Figure 11.3 Left: The structure of the algorithm Halts. It takes two parameters, an algorithm (Alg) and its input (Inp), and tests whether the algorithm applied to the input Alg(Inp) terminates. Middle: Application of Halts to the algorithm Loop and number 1, which results in “yes.” Right: Application of Halts to Loop and the number 2, which results in “no.”

  Figure 11.4 Left: The definition of the algorithm Selfie. It takes an algorithm (Alg) as a parameter and tests whether the algorithm applied to itself terminates. In that case Selfie will enter a nonterminating loop. Otherwise, it will stop. Middle: Application of Selfie to itself leads to a contradiction: If Selfie applied to itself terminates, then it goes into a nonterminating loop, that is, it doesn’t terminate; if it doesn’t terminate, it stops, that is, it terminates. Right: Expanding the definition of Halts provides a slightly different view of the paradox.

  The resulting flowchart describes a computation that seems to behave as follows. If Selfie applied to itself halts, it runs forever, whereas if it doesn’t halt, it stops. The contradiction may become even more obvious if we replace the call of Halts by its definition, as shown in the right graphic in figure 11.4. So, does Selfie(Selfie) terminate or not?

  Let’s assume it does. In that case, the algorithm Halts—which we assume can correctly determine whether an algorithm halts on a specific input—will say that Selfie(Selfie) halts, but that will cause Selfie(Selfie) to select the “yes” branch of the conditional and enter the nonterminating loop. This means, if Selfie(Selfie) terminates, it doesn’t terminate. So that assumption is clearly wrong. Let’s then assume that Selfie(Selfie) doesn’t terminate. In this case, Halts yields false, causing Selfie(Selfie) to select the “no” branch of the conditional and halt. This means if Selfie(Selfie) doesn’t terminate, it terminates. This is wrong as well.

  Thus if Selfie(Selfie) halts, it runs forever, and if it doesn’t halt, it halts—a contradiction in either case. This can’t be true. So what went wrong here? Except for standard control structures (loop and conditional), all we have used in constructing the algorithm Selfie is the assumption that the algorithm Halts can correctly determine the termination behavior of algorithms. Since this assumption has led to a contradiction, it must be wrong. In other words, the algorithm Halts cannot exist, because assuming its existence leads to a logical contradiction.

  This way of reasoning is reminiscent of logical paradoxes. For example, let’s consider the following variation of the well-known barber paradox.2 Suppose Punxsutawney Phil can see the shadow of only those groundhogs that can’t see their own shadow. The question is, Can Punxsutawney Phil see his own shadow? Let’s assume that he can. In that case, he does not belong to the groundhogs that can’t see their own shadow, but these are the only groundhogs whose shadow he can see. Since he is not one of them, he can’t see his own shadow, which is a contradiction to our assumption. So let’s assume he can’t see his own shadow. But now he is one of those groundhogs whose shadow he can see, again a contradiction to the assumption. So, no matter what we assume, we obtain a contradiction, which means that a groundhog that fits the given description cannot exist. In the same way, there cannot be an algorithm that fits the description of Halts.

  As with the example of searching for a picture in a book, we can judge the termination behavior of particular algorithms quite well. Doesn’t this contradict the fact that the algorithm Halts cannot exist? No, it only shows that we can solve the halting problem for particular cases, which doesn’t imply that there is a single method for doing so in all cases.

  The nonexistence of an algorithm Halts is a surprising but also profound insight. It tells us that there are computational problems that cannot be solved algorithmically. In other words, there are computational problems that computers cannot solve—ever. Such problems for which no algorithms exist are called uncomputable or undecidable.3

  Learning about the existence of undecidable/uncomputable problems might be disappointing if you thought that every mathematical or computational problem could be solved automatically. But maybe there are only a few such cases, and for the majority of problems algorithms do exist? Unfortunately, that is not the case. In fact, the overwhelming majority of problems are undecidable. It is not easy to fathom this point because it involves two different notions of infinity.4 To visualize the difference, think of a two-dimensional grid that extends infinitely in all directions. Each decidable problem can be placed on one grid point. There are infinitely many grid points, so the number of decidable problems is really large. But the number of undecidable problems is even larger; it is so large that we couldn’t place the problems on the grid points. There are so many of them that if we placed them on the plane together with the decidable problems, they would occupy all the space between the grid points. If you consider a small portion of the grid, say, a small square spanned by four grid points, for these four decidable problems, there are infinitely many undecidable problems that fill the space between them.

  The fact that most problems cannot be algorithmically solved is certainly sobering news, but it also provides us with deep insight into the fundamental nature of computer science as a discipline. Physics reveals to us important limitations about space, time, and energy. For example, the first law of thermodynamics about the conservation of energy says that energy cannot be created or destroyed; it can only be transformed. Or, according to Einstein’s special theory of relativity, information or matter cannot be transmitted faster than the speed of light. Similarly, knowledge about (un)decidable problems shows us the scope and limits of computation. And knowing one’s limits is probably as important as knowing one’s strengths; in words attributed to Blaise Pascal, “We must learn our limits.”

  Further Exploration

  The movie Groundhog Day has illustrated different aspects of a loop. A crucial feature in the movie is the question of whether the loop will ever end. In the movie, the protagonist Phil Connors tries to find a combination of actions that will end the loop. Similarly, in the movie Edge of Tomorrow, an Army public relations officer named Bill Cage, who dies while reporting about an alien invasion of earth, is repeatedly sent back in time to the previous day to relive the experience. In contrast to Groundhog Day, where every loop iteration takes exactly one day, later iterations in Edge of Tomorrow take Bill Cage further into the day and delay his death as he is trying out alternative actions in every iteration. (The movie is also known under the title Live. Die. Repeat., making the loop algorithm obvious.) This is similar to replaying a video game over and over again, learning from past mistakes and trying to reach a higher level each time. Dark Souls is a video game that exploits this phenomenon and makes it a feature of its game play. The novel Replay, by Ken Grimwood, also contains characters who relive parts of their lives. However, the relived episodes get shorter and shorter, ending always at the same time and starting closer to the end point. Moreover, the people have no
control over their replays. This is also the case for the protagonist in the movie Source Code, where a passenger on a commuter train into Chicago is in an eight-minute time loop, trying to prevent a bomb attack. In this story, the protagonist himself has no control over the loop, since it is a computer simulation managed from the outside.

  A loop works by changing in each iteration parts of an underlying state until the termination condition for the loop is fulfilled. Relevant for the effect and termination of a loop are only those parts of the state that transcend each iteration. In the case of Groundhog Day, the state that can be changed is only the person Phil Connors. Everything else (the physical surroundings, the memories of other people, etc.) is reset on each iteration and cannot be affected by Phil Connors. Analyzing a story from this perspective helps uncover implicit assumptions about the effect of actions, memories of people, and so on, and thus supports the understanding of the story. It also helps with discovering inconsistencies and plot holes.

  When the actions in a loop don’t affect the parts of the state that can make the termination condition true, a loop will not terminate. The movie Triangle seems essentially to consist of one big nonterminating loop. However, since some of the actors have doppelgängers, the loop structure is actually more intricate and indicates the existence of several interleaved loops. A nonterminating loop is displayed most prominently in the story of Sisyphus. According to Greek mythology, Sisyphus was punished by Zeus by forcing him endlessly to push a boulder up a hill. When he reaches the top of the hill, the boulder rolls down again, and Sisyphus has to begin all over again. The story of Sisyphus is interpreted philosophically in Albert Camus’s The Myth of Sisyphus, which contemplates how to live in a world that is ultimately devoid of meaning and where no action can have any lasting effects.

  Recursion

  Back to the Future

  Read This Again

  You are back in your office and have several phone calls to make. Calling someone is simply a matter of a few clicks on your smartphone, or you might ask an electronic assistant to initiate the call for you. But without a computer to help, you would have to find the number in a phone book. How do you do that? You probably won’t start on the first page and search through all the names one by one, that is, you won’t treat the phone book as a list. Instead you will probably open the phone book somewhere in the middle and compare the name you are looking for with the one you see. You may get lucky and immediately find the name on the current page. If so, you are done. Otherwise, you will continue your search either before or after the current position, again by opening a page somewhere in the middle of the identified unexplored page range. In other words, you will employ binary search to find the phone number. The same algorithm is used to find a word in a printed dictionary or a book among the shelves in a library.

  This algorithm, discussed in some detail in chapter 5, is recursive, since it occurs as part of itself. This becomes clear when you try to explain the algorithm to somebody else. After describing the steps of the first round (opening the book, comparing the name, deciding whether to search forward or backward), you need to explain that the same steps have to be repeated again. You could say, for example, “Then repeat these actions.” It is the compound noun “these actions” that refers to what needs to be repeated. If we decide to give a name to the whole algorithm, say BinarySearch, then we can actually use this name in the instruction: “Then repeat BinarySearch” to express the repetition in the algorithm. Employing the name BinarySearch in this way results in a definition of the algorithm that uses that name in its own definition, and this is what descriptive recursion is: it uses a name or symbol or some other mechanism to express self-reference, that is, to refer to itself in its definition.

  When executed, the algorithm leads to the repetition of a few steps (for example, opening a book on a particular page or comparing names) potentially many times. In this respect, recursion is similar to a loop, which also causes the repetition of the steps of an algorithm. Does it matter whether we employ a loop or recursion in an algorithm? As far as the computation itself is concerned, it doesn’t—any computation that is described using recursion can also be represented using loops, and vice versa. However, the understanding of an algorithm is affected by the way it is expressed. In particular, divide-and-conquer problems such as binary search or quicksort are often most easily expressed using recursion because the recursion is not linear, that is, the algorithm is referenced recursively more than once. In contrast, computations that repeat a fixed set of actions until a condition is fulfilled, which corresponds to linear recursion, are often most easily described by loops.

  But recursion does not only appear in algorithms as a descriptive phenomenon; sequences of values can themselves be recursive. If you are singing “99 bottles of beer on the wall” while searching the dictionary, this would emphasize the recursive nature of the process. There are two versions of this song, one that stops once you’ve counted down to zero, and one that recurses back to 99 and starts all over again. Unlike physical embodiments of recursion, such as the Matryoshka dolls, which always terminate at a certain point, linguistic recursion may go on forever. Binary search does terminate, since sooner or later either the name is found or you run out of pages to search, but never-ending songs, as their name suggests, do not—at least, if understood strictly algorithmically.

  Here is an experiment to illustrate this point. See whether you can perform the simple task described in the following sentence:

  Read this sentence again.

  If you are reading this sentence now, you didn’t follow the instructions of the task; otherwise you wouldn’t have come this far. Just as you aborted the fruitless search for your colleague’s office, you have made a decision outside of the algorithm (the preceding sentence in this case) to stop executing the algorithm. Just as loops are prone to nontermination, so are recursive descriptions, and detecting nontermination is algorithmically impossible for recursion, as it is for loops.

  Chapter 12 explains different forms of recursion using time travel as a metaphor. By taking a close look at paradoxes—in time travel and in recursion—we can better understand what the meaning of a recursive definition is.

  12

  A Stitch in Time Computes Fine

  The word recursion has two different meanings, which can be a source of confusion about the concept. Since recursion plays an important role in the description of computation, it should be understood well. While recursion in algorithms can be replaced by loops, recursion is actually more fundamental than loops because, in addition to defining computations, it is also used for defining data. The definitions of lists, trees, and grammars all require recursion; there is no alternative version that is based on loops. This means if one had to decide between the two concepts and pick only one, it would have to be recursion, because many data structures depend on it.

  Deriving from the Latin verb recurrere, which roughly means “run back,” the word recursion is used to indicate some form of self-similarity or self-reference. These two different meanings lead to different notions of recursion.

  Self-similarity can be found in pictures that contain themselves in smaller form, such as the picture of a room that contains a TV that displays the same view of the room, including a smaller version of the TV that shows the room, and so on. In contrast, self-reference occurs when a definition of a concept contains a reference to itself, usually through the use of a name or symbol. As an example consider the definition of descendant (which was used as a basis for an algorithm for computing descendants in chapter 4). Your descendants are all your children and the descendants of your children. Here the definition of what your descendants are includes a reference to the word descendant.

  In this chapter I present different forms of recursion and specifically explain the relationship between the self-similarity and self-reference forms of recursion. I use the movie trilogy Back to the Future and the idea of time travel to illustrate several aspects conce
rning recursion. Time travel can be viewed as a mechanism that works like recursion in describing sequences of events. Starting from the observation that recursive definitions can be understood as time travel instructions, I explain the problem of time paradoxes and how it is related to the question of making sense of recursive definitions through the concept of fixed points.

  This chapter also points out several features of recursion. For example, the TV room recursion is direct in the sense that the picture of the room is immediately contained as part of itself. Moreover, the recursion is unbounded, that is, the containment goes on forever, so that if we could repeatedly zoom in and expand the TV screen to the size of the picture, we would never reach an end of the containment. This chapter examines examples of indirect and bounded recursions and explores their impact on the concept of recursion.

  Finally, I explain the close relationship between loops and recursion by demonstrating how algorithms involving loops, such as Hansel and Gretel’s pebble-tracing algorithm, can also be described using recursion. I show that loops and recursion are equivalent in the sense that any algorithm that uses a loop can always be transformed into an algorithm that computes the same result using recursion, and vice versa.

  It’s about Time

  Like many stories about time travel, the movie trilogy Back to the Future employs time travel as a means for solving problems. The general idea is to identify a past event as the cause of a problem in the present and go back in time to change the event, hoping that the ensuing events then unfold differently and avoid the problem. In the Back to the Future story, the scientist Doc Brown has invented a time machine in 1985, which lets him and his friend Marty McFly, a high school student, experience a number of adventures. In the first movie, Marty by accident goes back to the year 1955 and interferes with his parents’ falling in love, which threatens his and his siblings’ existence. He is ultimately able to restore (most of) the course of history and safely return to 1985. In the second movie, Marty, his girlfriend Jennifer, and Doc Brown return from a trip to 2015, in which they had to rectify a problem with Marty and Jennifer’s children. They find a dark and violent 1985 in which Biff Tannen, Marty’s antagonist from the first movie, has become a rich and powerful man. Biff has murdered Marty’s father and married Marty’s mother. Biff built his wealth with a sports almanac from 2015 that predicts the outcomes of sports events. He had stolen the almanac from Marty in 2015 and given it to his younger self by traveling to 1955 with the help of the time machine. To restore the reality of 1985 to what it was before they left for 2015, Marty and Doc Brown travel back to 1955 to take the sports almanac away from Biff.