Chapter 1: Introduction

Computer science is to the information revolution what mechanical engineering was to the industrial revolution.

—Robert Keller

1.1 What is Computer Science?

You might be uncertain about what computer science (CS) is, but you use it every day. When you use Google or your smartphone, or watch a movie with special effects, there’s lots of CS in there. When you order a product over the Internet, there is CS in the web site, in the cryptography used to keep your credit card number secure, and in the way that FedEx routes their delivery vehicle to get your order to you as quickly as possible. Nonetheless, even computer scientists can struggle to answer the question “What exactly is CS?”

Many other sciences try to understand how things work: physics tries to understand the physical world, chemistry tries to understand the composition of matter, and biology tries to understand life. So what is computer science trying to understand? Computers? Probably not: computers are designed and built by humans, so their inner workings are known (at least to some people!).

Perhaps it’s all about programming. Programming is indeed important to a computer scientist, just as grammar is important to a writer or a telescope is important to an astronomer. But nobody would argue that writing is about grammar or that astronomy is about telescopes. Similarly, programming is an important piece of computer science but it’s not what CS is all about.

If we turn to origins, computer science has roots in disparate fields that include engineering, mathematics, and cognitive science, among others. Some computer scientists design things, much like engineers. Others seek new ways to solve computational problems, analyze their solutions, and prove that they are correct, much like mathematicians. Still others think about how humans interact with computers and software, which is closely related to cognitive science and psychology. All of these pieces are a part of computer science.

../_images/Alien7.PNG

Zoogenesis refers to the origin of a particular animals species. Computational biology is a field that uses CS to help solve zoogenetic questions, among many others.

One theme that unifies (nearly) all computer scientists is that they are interested in the automation of tasks ranging from artificial intelligence to zoogenesis. Put another way, computer scientists are interested in finding solutions for a wide variety of computational problems. They analyze those solutions to determine their “goodness,” and they implement the good solutions to create useful software for people to work with. This diversity of endeavors is, in part, what makes CS so much fun.

There are several important concepts at the heart of computer science; we have chosen to emphasize six of them: data, problem solving, algorithms, programming, abstraction, and creativity.

1.1.1 Data

../_images/Alien7.PNG

That’s Astronomical!

When you Google the words “pie recipe,” Google reports that it finds approximately 38 million pages, ranked in order of estimated relevance and usefulness. Facebook has approximately 1 billion active users who generate over 3 billion comments and “Likes” each day. GenBank, a national database of DNA sequences used by biologists and medical researchers studying genetic diseases, has over 100 million genetic sequences with over 100 billion DNA base pairs. According to the International Data Corporation, in 2010 the size of our “Digital Universe” reached 1.2 zettabytes. How much is that? Jeffrey Heer, a computer scientist who specializes in managing and visualizing large amounts of data, puts it this way: A stack of DVDs that reached to the moon and back would store approximately 1.2 zettabytes of data.

Without computer science, all of this data would be junk. Searching for a recipe on Google, a friend on Facebook, or genes in GenBank would all be impossible without ideas and tools from computer science.

Doing meaningful things with data is challenging, even if we’re not dealing with millions or billions of things. In this book, we’ll do interesting things with smaller sets of data. But much of what we’ll do will be applicable to very large amounts of data too.

1.1.2 Algorithms

Making Pie and Making \(\pi\)

When presented with a computational problem, our first objective is to find a computational solution, or “algorithm,” to solve it. An algorithm is a precise sequence of steps for carrying out a task, such as ranking web pages in Google, searching for a friend on Facebook, or finding closely related genes in Genbank. In some cases, a single good algorithm is enough to launch a successful company (e.g., Google’s initial success was due to its Page Rank algorithm).

Algorithms are commonly compared to recipes that act on their ingredients (the data). For example, imagine that an alien has come to Earth from a distant planet and has a hankering for some pumpkin pie. The alien does a Google search for pumpkin pie and finds the following:

../_images/Alien7.PNG

I’ve come to Earth for pumpkin pie!

  1. Mix 3/4 cup sugar, 1 tsp cinnamon, 1/2 tsp salt, 1/2 tsp ginger and 1/4 tsp cloves in a small bowl.
  2. Beat two eggs in a large bowl.
  3. Stir 1 15-oz. can pumpkin and the mixture from step 1 into the eggs.
  4. Gradually stir in 1 12 fl. oz. can evaporated milk into the mixture.
  5. Pour mixture into unbaked, pre-prepared 9-inch pie shell.
  6. Bake at 425°F for 15 minutes.
  7. Reduce oven temperature to 350°F.
  8. Bake for 30-40 minutes more, or until set.
  9. Cool for 2 hours on wire rack.
../_images/Alien7.PNG

No! Don’t lick the spoon - there are raw eggs in there!

Assuming we know how to perform basic cooking steps (measuring ingredients, cracking eggs, stirring, licking the spoon, etc.), we could make a tasty pie by following these steps precisely.

Out of respect for our gastronomical well-being, computer scientists rarely write recipes (algorithms) that have anything to do with food. As a computer scientist, we would be more likely to write an algorithm to calculate \(\pi\) very precisely than we would be to write an algorithm to make a pie. Let’s consider just such an algorithm:

  1. Draw a square that is 2 by 2 feet.
  2. Inscribe a circle of radius 1 foot (diameter 2 feet) inside this square.
  3. Grab a bucket of n darts, move away from the dartboard, and put on a blindfold.
../_images/Alien7.PNG

Please don’t try this at home!

  1. Take each dart one at a time and for each dart:

    1. With your eyes still covered, throw the dart randomly (but assume that your throwing skills ensure that it will land somewhere on the square dartboard).
    2. Record whether or not the dart landed inside the circle.
  2. When you have thrown all the darts, divide the number that landed inside the circle by the total number, n, of darts you threw and multiply by 4. This will give you your estimate for \(\pi\).

Figure 1.1 shows the scenario.

../_images/dart.PNG

Figure 1.1: Using a dartboard to approximate \(\pi\)

../_images/Alien7.PNG

Hey, watch it! That dart almost hit me!

That’s the description of the algorithm, but why does it work? Here’s why: The area of the circle is \(\pi r^2\) which is π in this case because we made the radius of the board to be 1. The area of the square is 4. Since we’re assuming that darts are equally likely to end up anywhere in the square, we expect the proportion of them that land in the circle to be the ratio of the area of the circle to the area of the square: \(\frac{\pi}{4}\). Therefore, if we throw n darts and determine that some number k land inside the circle, then \(\frac{k}{n}\) should be approximately \(\frac{\pi}{4}\). So multiplying the ratio by 4 gives us an approximation of \(\pi\).

Happily, the computer does not have to robotically throw physical darts; instead we can simulate this dart throwing process on a computer by generating random coordinates that describe where the darts land. The computer can throw millions of virtual darts in a fraction of a second and will never miss the square–making things considerably safer for your roommate!

1.1.3 Programming

Although we noted earlier that computer science is not exclusively about programming, ultimately we usually want to have a program–that is, software–that implements the algorithm that will operate on our data.

Learning to program is a bit like learning to speak or write in a new language. The good news is that the syntax of a programming language–the vocabulary and grammar–is not nearly as complicated as for a spoken language. In this book, we’ll program in a language called Python, whose syntax is particularly easy to learn. But don’t be fooled into thinking it’s not a real programming language–Python is a very real language used by real programmers to write real software. Moreover, the ideas that you’ll learn here will be transferable to learning other languages later.

1.1.4 Abstraction

While data, algorithms, and programming might seem like the whole story, the truth is that there are other important ideas behind the scenes. Software is often immensely complex and it can be difficult or even impossible for any single person to keep all of the interacting pieces in mind. To deal with such complex systems, computer scientists use the the notion of abstraction–the idea that when designing one part of a program, we can ignore the inessential details of other parts of the program as long as we have a high level understanding of what they do.

For example, a car has an engine, a drivetrain, an electrical system, and other components. These components can be designed individually and then assembled to work together. The designer of the drivetrain doesn’t need to understand every aspect of how the engine works, but just enough to know how the drivetrain and the engine will be connected. To the drivetrain designer, the engine is an “abstraction.” In fact, the engine itself is divided into components such as the engine block, distributor, and others. These parts too can be viewed as abstract entities that interact with one another. When designing the engine block, we don’t need to think about every detail of how the distributor works.

Software systems can be even more complicated than a car. Designing software requires that we think about abstractions in order to ensure that many people can contribute to the project without everyone needing to understand everything, in order to test the software methodically, and in order to be able to update it in the future by simply replacing one “component” by a new and improved component. Abstraction, therefore, is a key idea in the design of any large system, and software in particular.

1.1.5 Problem Solving and Creativity

This book strives to prepare you to write well-designed programs that do interesting things with data. In the process, we hope to convey to you that computer science is an enormously creative endeavor that requires innovative problem-solving, exploration, and even experimentation. Often times, there’s more than one way to solve a problem. In some cases there’s not even a clear “best” way to solve a problem. Different solutions will have different merits. While Google, Facebook, GenBank are wonderfully easy to use, many challenges arose–and continue to arise–in the design and continual updating of such systems. These challenges often lead to groups of computer scientists working together to find different solutions and evaluate their relative merits. While the challenges that we’ll confront in this book are of a more modest scope, we hope to share with you the sense of problem solving and creativity that are at the heart of computer science.

Takeaway message: In a nutshell, the objective of this book is to demonstrate the breadth of activities that comprise computer science, show you some fundamental and beautiful ideas, and provide you with the skills to design, implement, and analyze your own programs.

1.2 PicoBot

Leap before you look.

—W.H. Auden

The best way for you to get a feel for computer science is to jump right in and start solving a computer science problem. So let’s do just that. In this section, we’ll examine solutions to an important problem: How to make sure you’ll never have to clean–or at least vacuum–your room again. To solve this problem we’ll use a simple programming language named Picobot that controls a robot loosely based on the Roomba vacuum cleaner robot.

../_images/Alien7.PNG

This web site offers a simulation environment for exploring Picobot’s capabilities

You’re probably wondering what happened to Python, the programming language we said we would be using throughout this book. Why are we sweeping Python under the carpet and brushing aside the language that we plan to use for the remainder of the book? The answer is that although Python is a simple (but powerful!) programming language that’s easy to learn, Picobot is an even simpler language that’s even easier to learn. The entire language takes only a few minutes to learn and yet it allows you to do some very powerful and interesting computation. So, we’ll be able to start some serious computer science before we get sucked into a discussion of a full-blown programming language. This will be new and fun–and whether you have programmed before, it should offer a “Eureka!” experience. So, dust off your browser and join us at http://www.cs.hmc.edu/picobot.

../_images/Alien7.PNG

Or, at least, the “breakout” app that enable the industry’s first large-scale profits.

../_images/roomba.jpg

An iRobot Roomba. You’ll notice that we use the word “Picobot” to refer to both the Roomba robot and the language that we will use to program it. Actually, Picobot might not be able to actually “see” at all. Instead, it might sense its environment though one of many possible sensors including bump sensors, infrared, camera, lasers, etc.

1.2.1 The Roomba Problem

It is the humblest of tasks–cleaning up–that has turned out to be the “killer app” for household robots. Imagine yourself as a Roomba vacuum named Picobot: your goal is to suck up the debris from the free space around you- ideally without missing any nooks or crannies. The robotics community calls this the coverage problem: it is the task of ensuring that all the grass is mown, all the surface receives paint, or all the Martian soil is surveyed.

At first this problem might seem pretty easy. After all, if your parents gave you a vacuum cleaner and told you to vacuum your room without missing a spot, you’d probably do a pretty great job without even thinking too much about it. Shouldn’t it be straightforward to convey your strategy to a robot?

Unfortunately, there are a couple of obstacles that make the Picobot’s job considerably more difficult than yours. First, Picobot has very limited “sight”; it can only sense what’s directly around it. Second, Picobot is totally unfamiliar with the environment it is supposed to clean. While you could probably walk around your room blindfolded without crashing into things, Picobot is not so lucky. Third, Picobot has a very limited memory. In fact, it can’t even remember which part of the room it has seen and which part it has not.

While these challenges make Picobot’s job (and our job of programming Picobot) more difficult, they also make the coverage problem an interesting and non-trivial computer science problem worth serious study.

1.2.2 The Environment

../_images/Alien7.PNG

“Discretize” is CS-speak for “break up into individual pieces”.

Our first task in solving this problem is to represent it in a way that the computer can handle. In other words, we need to define the data we will be working with to solve this problem. For example, how will we represent where the obstacles in the room are? Where Picobot is? We could represent the room as a plane, and then list the coordinates of the object’s corners and the coordinates of Picobot’s location. While this representation is reasonable, we will actually use a slightly simpler approach.

Whether lawn or sand, an environment is simpler to cover if it is discretized into cells as shown in Figure 1.2. This is our first example of an abstraction: we are ignoring the details of the environment and simplifying it into something we can easily work with. You, as Picobot, are similarly simplified: you occupy one grid square (the green one), and you can travel one step at a time in one of the four compass directions: north, east, west, or south.

Picobot cannot travel onto obstacles (the blue cells–which we will also call–”walls”); as we mentioned above, it does not know the positions of those obstacles ahead of time. What Picobot can sense is its immediate surroundings: the four cells directly to its north, east, west, or south. The surroundings are always reported as a string of four letters in “NEWS” order, meaning that we first see what is in our neighboring cell to the North, next what’s to the East, then West, and finally South. If the cell to the north is empty, the letter in the first position is an x. If the cell to the north is occupied, the letter in that first position is an N. The second letter, an x or an E, indicates whether the eastern neighbor is empty or occupied; the third, x or W, is the west; the fourth, x or S, is the south. At its position in the lower-left-hand corner of Figure 1.2, for example, Picobot’s sensors would report its four-letter surroundings as xxWS. There are sixteen possible surroundings for Picobot, shown in Figure 1.3 with their textual representations.

../_images/picoRules.jpg

Figure 1.2: There are four types of cells in a Picobot environment, or map: green is Picobot itself, blue cells are walls, and gray cells are free space. Picobot can’t sense whether a empty cell has been visited or not (dark or light gray), but it can sense whether each of its four immediate neighbors is free space or an obstacle.

../_images/picoPossibilities.jpg

Figure 1.3: There are sixteen possible surroundings strings for Picobot. The one in which Picobot is completely enclosed will not occur in our simulator!

1.2.3 State

As we’ve seen, Picobot can sense its immediate surroundings. This will be important in its decision-making process. For example, if Picobot is in the process of moving north and it senses that the cell to its north is a wall, it should not try to continue moving north! In fact, the simulator will not allow it.

../_images/Alien7.PNG

I’m currently in an inquisitive state.

But how does Picobot “know” whether it is moving north or some other direction? Picobot doesn’t have an innate sense of direction. Instead, we make use of a powerful concept called state. The state of a computer (or a person or almost any other thing) is simply its current condition: on or off, happy or sad, underwater or in outer space, etc. In computer science, we often use “state” to refer to the internal information that describes what a computer is doing.

Picobot’s state is extremely simple: it is a single number in the range 0-99. Somewhat surprisingly, that’s enough to give Picobot some pretty complex behaviors. Picobot always starts in state 0.

../_images/Alien7.PNG

The state of anything can be described with a set of numbers.. but describing human states would take at least trillions of values

Although Picobot’s state is numeric, it’s helpful to think of it in English terms. For example, we might think of state 0 as meaning “I’m heading north until I can’t go any further.” However, it’s important to note that none of the state numbers has any special built-in meaning; it is up to us to make those decisions. Moreover, Picobot doesn’t actually have a sense of which directions it is pointing. But we can define our own conception of which direction Picobot is “pointing” by defining an appropriate set of states.

For example, imagine that Picobot wants to perform the task of continually moving north until it gets to a wall. We might decide that state 3 means “I’m heading north until I can’t go any further (and when I get to a wall to my north, then I’ll consider what to do next!).” When Picobot gets to a wall, it might want to enter a new state such as “I’m heading west until I can’t go any further (and when I get to a wall to my west, I’ll have to think about what to do then!).” We might choose to call that state 42 (or state 4; it’s entirely up to us).

../_images/states.PNG

Figure 1.4: The five parts of two Picobot rules. One useful way to interpret the idea of state is to attribute a distinct intention to each state. With these two rules, Picobot’s initial state (state 0) represents “go west as far as possible.”

As we’ll see next, your job as the Picobot programmer is to define the states and their meanings; this is what controls Picobot and makes it do interesting things!

Takeaway message: The state is simply a number representing a task that you would like Picobot to undertake.

1.2.4 Think locally, act globally

Now we know how to represent Picobot’s surroundings, and how to represent its state. But how do we make Picobot do anything?

Picobot moves by following a set of rules that specify actions and possibly state changes. Which rule Picobot chooses to follow depends on its current state and its current surroundings. Thus, Picobot’s complete “thought process” is as follows:

  1. I take stock of my current state and immediate surroundings.
  2. Based on that information, I find a rule that tells me (1) a direction to move and (2) the state I want to be in next.

Picobot uses a five-part rule to express this thought process. Figure 1.4 shows two examples of such rules.

The first rule,

0 xxWx -> E 1

re-expressed in English, says “If I’m in state 0 and only my western neighbor contains an obstacle, take one step east and change into state 1.” The second rule,

0 xxxx -> W 0
../_images/Alien7.PNG

Go west, young Picobot!

says “If I’m in state 0 with no obstacles around me, move one step west and stay in state 0.” Taken together, these two rules use local information to direct Picobot across an open area westward to a boundary.

../_images/movingPico.jpg

Figure 1.5: The result of running Picobot with this section’s four rules.

../_images/Alien7.PNG

Remember that Picobot always begins its mission in state 0

At each step, Picobot examines the list of rules that you’ve written looking for the one rule that applies. A rule applies if the state part of the rule matches Picobot’s current state and the surroundings part of the rule matches the current surroundings. What happens if there are NO rules that match Picobot’s current state and surroundings? The Picobot simulator will let you know about this in its Messages box and the robot will stop running. Similarly, if more than one rule applies, Picobot will also complain. Figure 1.5 shows how Picobot follows the first rule that matches its current state and surroundings at each time step. But what about state 1? No rules specify Picobot’s actions in state 1-yet! Just as state 0 represents the “go west” task, we can specify two rules that will make state 1 be the “go east” task:

1 xxxx -> E 1

1 xExx -> W 0

../_images/Alien7.PNG

Picobot cannot sense whether or not a cell has been visited. This limitation is quite realistic: the Roomba, for example, does not know whether a region has already been cleaned.

These rules transition back to state 0, creating an infinite loop back and forth across an open row. Try it out! Note that the Picobot website starts Picobot at a randomly selected empty cell. Note also that if Picobot starts along a top or bottom wall, no rules match and it does not move! We will remedy this defect in the next section.

../_images/picoTable.PNG

Table 1.1: Two equivalent formulations of a more general “go-west-go-east” behavior for Picobot. Both sets of rules use only two states, but the wildcard character * allows for a much more succinct representation on the left than on the right!

By the way, sometimes you might not want Picobot to move as the result of applying a rule. Rather than specifying a move direction (“E”, ‘W”, “N”, or “S”), you may use the upper-case letter “X” to indicate “stay where you are”. For example, the rule

0 Nxxx -> X 1

is saying “if I’m in state 0 and there is a wall to the north, don’t move but enter state 1.”

1.2.5 Whatever

The problem with the previous “go-west-go-east” example is that the rules are too specific. When going west, we really don’t care whether or not walls are present to the north, south, or east. Similarly, when going east, we don’t care about neighboring cells to the north, south, or west. The wildcard character * indicates that we don’t care about the surroundings in the given position (N, E, W, or S). Table 1.1’s rules use the wildcard to direct Picobot to forever visit (vacuum) the east-west row in which it starts.

../_images/Alien7.PNG

Picobot needs to get over its “don’t care” attitude!

1.2.6 Algorithms and Rules

So far we’ve looked at how to write rules that make Picobot move. But in trying to solve problems with Picobot, it’s usually helpful to take a more global view of how Picobot is accomplishing its task, and then to translate that approach into rules. In other words, we want to develop an algorithm that allows Picobot to accomplish the desired task, where that task is usually to cover the entire room. In the previous section, Picobot had the more modest goal of simply moving back and forth in an empty room. The algorithm for accomplishing this task was the following:

  1. Move west until Picobot hits a wall to the west
  2. Then move east until Picobot hits a wall to the east
  3. Then go back to step 1

Now the question becomes: how do we translate this algorithm into the rules from the previous section:

0 **x* -> W 0

0 **W* -> E 1

1 *x** -> E 1

1 *E** -> W 0

As written, it is difficult to see the connection between the steps of the algorithm and the Picobot rules. We can see that Picobot will need two states to keep track of which direction it is moving (i.e., is it in step 1 or step 2), but it’s still not exactly clear how the algorithm translates into precise rules. Essentially, each of Picobot’s rules applies in an “if-then” fashion. In other words, if Picobot is in a particular state and sees a particular environment, then it takes a certain action and potentially enters a new state. With some minor modifications, we can rewrite the algorithm above to follow Picobot’s “if-then” rule structure more directly:

  1. Repeat the following steps forever:

    1. If Picobot is moving west and there is no wall to the west, then keep moving west.
    2. If Picobot is moving west and there is a wall to the west, then start moving east.
    3. If Picobot is moving east and there is no wall to the east, then keep moving east.
    4. If Picobot is moving east and there is a wall to the east, then start moving west.

Now we can see more clearly the direct translation between the steps of this algorithm and the Picobot rules: each step in the algorithm translates directly into a rule in Picobot, where state 0 represents “Picobot is movingWest” and state 1 represents “Picobot is moving East”. Formulating algorithms in this way is the key to writing successful programs in Picobot.

1.2.7 The Picobot challenge

../_images/Alien7.PNG

This back-and-forth nwonk saw euqinhcet to ancient Greek ox- ti dellac ohw srevird “boustrophedon.” Text in some classical nwonk si stpircsunam to show the same .nrettap

Table 1.1’s rules direct Picobot to visit the entirety of its starting row. This section’s challenge is to develop a set of rules that direct Picobot to cover the entirety of an empty rectangular room, such as the rooms in Figure 1.2 and 1.5. The set of rules–that is, your program–should work regardless of how big the room is and regardless of where Picobot initially begins.

Because Picobot does not distinguish already-visited from unvisited cells, it may not know when it has visited every cell. The online simulator, however, will detect and report a successful, complete traversal of an environment.

Try it out. You might find it helpful to simply play around with modifying the rules we’ve given you here. For example, you might start by altering the rules in Figure 1.1 so that they side-step into a neighboring row after clearing the current one. However, once you have an idea for how you might solve the problem, we encourage you to plan your algorithm, and then express that algorithm in a way that is easily translatable into Picobot rules.

../_images/Alien7.PNG

Thank you for sparing us from any corny maize jokes.

1.2.8 A-Maze Your Friends!

Once you’ve developed a Picobot program that completely traverses the empty room, try to write other programs for more complex environments. You’ll see a “MAP” option on the Picobot Web page where you can scroll forward or backward through a collection of maps that we’ve created. You can also edit these maps by clicking on a cell with your mouse; clicking on an empty cell turns it into a wall and clicking on a wall turns it into an empty cell. Remember that your program should work no matter where Picobot begins.

../_images/maze.jpg

Figure 1.6: Picobot’s maze.

One environment that is particularly interesting is the maze shown in Figure 1.6. Notice that in this maze, all the walls are connected to the outer boundary and all empty cells are adjacent to a wall. A smaller maze with this property is shown in Figure 1.7(a). Any maze with this property can be completely explored with a simple algorithm called the right-hand rule (or the left-hand rule if you prefer).

Imagine for a moment that you are in the maze rather than Picobot. In contrast to Picobot, you have a clear sense of the direction you’re pointing and you have two hands. You start facing north with your right hand touching the wall. Now, you can visit every empty cell by simply walking through the maze, making sure that your right hand is always touching the wall. Pause here for a moment to convince yourself that this is true. Notice also that this algorithm will not visit every cell if some walls are not connected to the outer boundary, as shown in the maze in Figure 1.7(b) or if some empty cells are not adjacent to a wall, as shown in Figure 1.7(c).

../_images/threemazes.jpg

Figure 1.7: (a) A maze in which all walls are connected to the outer boundary and all empty cells are adjacent to a wall. (b) A maze in which some walls are not connected to the outer boundary. (c) A maze in which some empty cells are not adjacent to walls.

Converting the right-hand rule into a set of Picobot rules is an interesting computational challenge. After all, you have a sense of direction and you have a right hand that was guiding you around the walls, whereas Picobot has neither hands nor a sense of orientation. To “teach” Picobot the right-hand rule, we’ll again need to use states to represent the direction that Picobot is pointing. It may seem that an impossibly large number of situations must be considered, but in fact, the number of situations is finite and actually quite small, which makes it possible to program Picobot for this task.

To get started, it seems pretty natural to use the four states 0, 1, 2, and 3 to represent Picobot pointing north, south, east, or west. Now, we’ll need to introduce rules that allow Picobot to behave as if it had a right hand to touch against the wall.

../_images/Alien7.PNG

Of course, all empty cells must be reachable. If some cells are isolated from others, the problem is just physically impossible.

Assume we are in state 0, which we (arbitrarily) choose to correspond to representing Picobot pointing north. Picobot’s imaginary right hand is then pointing east. If there is a wall to the east and none to the north, the right-hand rule would tell us to take a step to the north and keep pointing north. Taking a step to the north is no problem. “Keep pointing north” means “stay in state 0.” On the other hand, if we are in state 0 and there is no wall to the east, Picobot should take a step to the east and think of itself as pointing to the east. “Pointing east” will mean changing to another state that is intended to encode that information. This is a fun challenge and we encourage you to stop here and try it. (Remember, your program should work regardless of where Picobot starts and for any maze with the property that all walls are connected to the outer boundary and all empty cells are adjacent to a wall.)

1.2.9 Uncomputable environments

Is it possible to write a Picobot program that will fully explore any room that we give it? Surprisingly, the answer is “no,” and it’s possible to prove that fact mathematically. Picobot’s computational capabilities aren’t enough to guarantee coverage of all environments. However, by adding one simple feature to Picobot, it can be programmed to fully explore any room. That feature is the ability to drop, sense, and pick up “markers” along the way.

The fact that computational challenges as elementary as Picobot lead us to provably unsolvable problems suggests that computation and computers are far from omnipotent. And by the time you’re done reading this book, you’ll have learned how to prove that certain problems are beyond the limits of what computers can solve.