Lauren Ipsum: A Story About Computer Science and Other Improbable Things
Page 10
Chapter 1: A Hidden Ally
Xor
When you say “A or B,” you mean that you want one of those two things, or maybe both! If you say “A xor B,” then you mean you want one and only one of those two things, not both. That’s why Xor keeps turning rainbow colors: Xor and the thing he’s currently resting on can’t be blue at the same time. If he’s sitting on a blue sign, then he must turn any color that isn’t blue! Not a great form of camouflage, is it?
Steganosaurus
Steganography is the art of hiding information inside other information, and it’s used in both the digital and the physical world. For example, you might hide a secret message by writing it with invisible ink on a piece of paper. With a computer program, you could even hide words inside sounds and pictures. A Steganosaurus is, therefore, a dinosaur that can hide itself anywhere.
Chapter 2: Sense and Sensibleness
Composing
Eponymous Bach is a composer, but she works with ideas instead of music. Composing is the act of combining small ideas into bigger ones to solve a problem in steps. Almost every idea is composed of smaller ideas. For example, multiplying whole numbers isn’t anything special. You can think of it as adding a number to itself and repeating:
2 × 3 = 6
2 + 2 + 2 = 6 (Add up three twos.)
See also Decomposing (Chapter 17; Chapter 17: Chasing Elegants) and Relating (Chapter 17; Relating). Composing, decomposing, and relating are problem-solving methods that lie at the root of all math, logic, and computer science.
Bach’s First Law of Eponymy
Don’t let any new idea escape without putting a name on it. A name is like a handle that makes the idea easier to use.
Bach’s second Law of Eponymy
It’s better to put a name on Ideas than on Things, because Ideas last longer.
Bach’s Third Law of Eponymy
As an idea becomes more useful and famous, its name becomes shorter and lowercase. This law eventually affected Eponymous’s friend, Andy Ampère, and his discovery about electricity.
Ampère
André-Marie Ampère discovered that when electricity flows through parallel wires, the wires will either attract or repel each other, causing the wires to bend. By measuring how much they bend, you can measure how much electricity is flowing. Ampère used this idea to lay the foundation for nearly everything we know about electricity, and we measure electrical current in amperes (or amps) in his honor. (See Bach’s Third Law of Eponymy for Eponymous’s theory on why we don’t call the unit an Ampère nearly as often.)
Sense vs. Sensibleness
Programmers and mathematicians sometimes use a pair of ideas, called the solution space and the problem space, to describe finding an answer to a problem.
Say you need to move a heavy box so you can unpack it; anything related to moving the box is in your problem space. Try to imagine every single thing you could possibly do to try to move that box. You could walk forward, walk backward, stick out your tongue, sing a song, write an equation, use a lever, call for help, look for a forklift, or do literally anything else you can think of. Write down as many of these possibilities as you can fit on a piece of paper.
Out of that huge space of possibilities, imagine only the ones that have a good chance of moving the box. Circle those with a red pen. The circled ones are in the solution space. They make sense because they would accomplish your goal, and the rest don’t make sense. Now, look again at all of the circled possibilities and think about which one is best (fastest, cheapest, easiest, most reliable, and so on). Underline that one in green. That’s the most sensible answer out of all the ones that make sense.
The point of this exercise is to avoid a very human, very common error: we tend to grasp at the first solution we think of and forget to consider other possibilities. This is what Eponymous means when she tells Laurie that the Wandering Salesman’s solution isn’t sensible. See also Hugh Rustic (Chapter 8; Chapter 8: More Than One Way to Do It) and Five Whys (Chapter 14; Chapter 14: In the Abstract).
Chapter 3: Rounding Error
Round Robin Algorithm
The Robins aren’t really evil—they’re just hungry. They cooperate in everything they do, taking turns and making sure the work is balanced among them. Sharing work is a great way to get things done faster, and computers can share work, too!
You can find the Round Robin method almost anywhere. Imagine a bus route that takes an hour to complete. If you put two buses on that route, a bus will arrive at each stop every 30 minutes. With three buses, you’d see a bus every 20 minutes, and four means you’d see one every 15 minutes. With five buses, you’d see one every 12 minutes, and so on. Just divide 60 (the number of minutes in an hour) by the number of buses to see how often a bus should come.
But you have to be careful to make sure the buses arrive at each stop at evenly spaced times. Five buses reaching one stop all at once wouldn’t be balanced. Also, if one bus breaks down and gets delayed, this could cause all the other buses to back up!
Chapter 4: What the Tortoise Said to Laurie
Recursion
Recursion is a way to repeat the same process over and over until you find the answer you’re looking for. When you use recursion, you run though the process, and if the answer is the one you want, you stop. If it’s not, you take the answer you found, plug it into the same process, and run it again.
Let’s look at an example of recursion in action right here in Userland. Recall from Chapter 10 that Jane Hecate has a single, gigantic book of names. The name Lauren starts with L, so Jane should find it in the L section of her book, but that could take a while with so many pages. If Jane wants a faster way to look for Lauren, she can divide the book into two equal halves and see if L is in the first half or the second half.
First half: {A, B, C, D, E, F, G, H, I, J, K, L, M}
Second half: {N, O, P, Q, R, S, T, U, V, W, X, Y, Z}
Since L is in the first half, Jane can then divide the first half of the book in half, giving her two quarters of the book to search.
First quarter: {A, B, C, D, E, F, G}
Second quarter: {H, I, J, K, L, M}
Lauren should be in the second quarter, so Jane can divide that quarter in half, giving her two eighths of the alphabet:
First eighth: {H, I, J}
Second eighth: {K, L, M}
Jane can continue dividing the letter groups containing L in half until eventually she ends up with just the L section. (How many more times would Jane have to divide a set of letters in half to find L?) This way of searching for a particular piece of information is called a binary search.
See also The Garden of Forking Paths (Chapter 19; Chapter 19: Branching Out) and Chasing Your Tail (Achilles and the Tortoise).
Achilles and the Tortoise
These two characters were used by a philosopher named Zeno of Elea almost 2,500 years ago to talk about infinity. From Aristotle to Lewis Carroll to Marvin Minsky to Douglas Hofstadter, mathematics is full of stories about their adventures. It’s Tortoises all the way down.
Chasing Your Tail
Chasing your own tail is not always a waste of time! In computer science, there’s a type of recursion that sounds a bit like running around in circles, and it’s quite useful. In tail recursion, you perform a process, then perform the process again on the result, and repeat until you reach the final answer. For example, Jane Hecate’s binary search for the L section of her book might look something like this:
Check the section of the book of names we have right now.
Do we only have the L section?
If so, then we’re done!
If not, then divide the book in half.
Look at the half of the list containing the L section, and repeat.
See also Recursion (Chapter 4: What the Tortoise Said to Laurie).
Infinity
When people say there’s an infinite amount of something, they mean there’s no limit to how much of that thing exists. W
hen Tortoise demonstrates how an infinite string can be less than two inches long, he shows that you can split that string into an infinite number of smaller pieces.
Infinity is big, bigger than you can imagine. But you can hold infinity in your mind simply by saying a few words. There are infinite odd numbers: 1, 3, 5, 7, and so on, up to forever. There are infinite even numbers, too: 0, 2, 4, 6, 8, and so on. No matter how hard you look, you will never find an odd number in the list of even numbers or an even number among the odd ones. That means there are at least two kinds of infinity: the even numbers and the odd numbers.
There are also infinite kinds of infinity. Think about all the numbers divisible by 3 and all the numbers not divisible by 3 (or 4, or 5). Now imagine all the numbers that no one else has thought of before. That’s another kind of infinity!
Infinite Regress
If you think about how you think, you might then start thinking about how you think about how you think, and then about how you think about how you think about how you think, and so on. This is a form of argument called infinite regress, and it can have no end. The first time you fall into this mental trap, it can be confusing or even scary. The trick is not to take it too seriously.
If you think this sounds related to recursion, you’re correct! It would be quite troubling to get stuck in a recursive process forever. In real computers, infinite recursion never actually happens because no computer can hold an infinite amount of information. When the computer runs out of room while working on something recursive, you never know what might happen. Laurie and Xor experienced this firsthand at Recursion Junction. See also Chasing Your Tail (Achilles and the Tortoise).
Chapter 5: Welcome to Symbol
Semantic Turnstile
╞ is a logical symbol that points the way to a truth. It’s kind of like the equal sign (=), except that it shows how ideas are related instead of numbers. If all the ideas to the left of the semantic turnstile are true, then the idea on the right is also true.
Say you have two ideas: (A) “You have the password” and (B) “You may enter.” You can compose these ideas together to make a rule:
(A → B) “IF you have the password, THEN you may enter.”
That is the rule that Ponens explained to Laurie at the gates of Symbol. (Placing two ideas on either side of that little arrow is another way to say, “IF A is true, THEN B is true.”)
But how do you know the rule is true? Maybe that’s not how you enter Symbol. So you have to show that both the rule (A → B), and the first idea, A, are true. In this case, we need to be sure that both the rule (“IF you have the password, THEN you may enter”) and the idea (“You have the password”) are true before we let anyone through the gate.
That’s what the semantic turnstile is for. We put the rule and the first idea on the left of the turnstile, and put the second idea (B, which is “You may enter” in this case) on the right:
(A → B), (A) ╞ (B)
This means “IF our rule is true and IF you actually have the password, THEN you may enter.”
Here’s the weirder part: you might have noticed that the turnstile looks a lot like an IF...THEN. IF everything to the left is true, THEN the idea on the right is true. So how do we know this rule as a whole is true? Do we need a turnstile for the turnstile?
(A → B), (A) ╞ (B) ╞ (C)
. . . and then a turnstile for that one, and for the next one?
(A → B), (A) ╞ (B) ╞ (C) ╞ (D) ╞ (E) ╞ (F) ╞ (G) . . .
In theory, you have to pass an infinite number of turnstiles before you know anything is true! It’s a wonder we are able to put our shoes on in the morning! So how do we know that anything is true? How do you know your milk will come out of the carton at breakfast tomorrow, or that your classroom won’t be on the roof when you get to school?
In practice, we simply trust that the rules we live by are true, since we’ve seen them work in the past. However, it can be fun and useful to poke into the rules, as Laurie did. Even if they turn out to make sense, you learn a lot about how they work. Poking at rules is a big part of what science is all about! See Infinite Regress (Chapter 4; Infinity) and It’s Only Logical (It’s Only Logical).
Ponens
His full name is Modus Ponendo Ponens, and he represents a type of logical argument. This type of argument can come to a logical conclusion, but that conclusion might not always be true. For example, here’s how Ponens decided that the gate to Symbol is secure:
If only people with passwords can enter, then our door is secure.
Only people with passwords have entered.
Therefore, our door is secure.
This conclusion may seem logical, but it’s not necessarily true. Logic is only as good as the assumptions it depends on. Someone, like Laurie, can say she is Eponymous Bach without actually being Eponymous Bach, and as long as she has the right password, she can waltz right into Symbol. In that case, all of the logic in the world won’t make that gate secure! See also Tollens (next) and Semantic Turnstile (Chapter 5: Welcome to Symbol).
Tollens
His full name is Modus Tollendo Tollens, and, like Ponens, he represents a type of logical argument. In fact, Tollens works a lot like Ponens, but backward. For example, here’s how Tollens might decide that his door is secure:
If our door was insecure, then people without passwords would enter.
No one without a password has entered.
Therefore, our door is secure.
This is how Tollens would decide Steganosauruses don’t exist:
If Steganosauruses existed, you would see them.
You have never seen a Steganosaurus.
Therefore, they do not exist.
Like Ponens, Modus Tollendo Tollens is perfectly valid logic, but it’s only as good as the assumptions it’s based on. Just because you don’t have proof that something is true, that doesn’t mean it’s automatically false, and just because you’ve never seen a Steganosaurus, that doesn’t mean they don’t exist. Maybe they live on an island you’ve never been to, or maybe they are so good at hiding that no one can see them. See It’s Only Logical (next).
It’s Only Logical
Even if an idea is logical, it might not be true. It’s easy for an idea to be simple, logical, and false—if you forget to consider all of the facts. For example, people who go swimming have wet hair when they’re finished. If you see someone with wet hair, does that mean she just got out of the pool? No! Perhaps it was raining outside, or maybe she just took a shower.
It’s also easy for logic to get stuck in endless loops. See Ponens (Ponens) and Infinite Regress (Chapter 4; Infinity).
Chapter 6: A Tinker’s Trade
Algorithm An algorithm is a set of specific steps that you can follow to solve a problem. For example, a recipe for how to make pizza is an algorithm:
Spread the dough into a pan.
Cover the dough in a layer of pizza sauce.
Sprinkle cheese on top of the sauce.
Bake the pizza for 20 minutes at 350 degrees Fahrenheit.
Take the pizza out of the oven and let it cool.
Dig in!
Just like that recipe, Laurie’s turtle drawing poems were algorithms. They broke down the process of drawing a circle into small steps, and the turtle followed those instructions to create circles of any size. If you really want to, you can even think up algorithms for algorithms, which is to say, how to figure out how to figure out how to do something. See Infinite Regress (Chapter 4; Infinity).
How would you tell Tinker’s turtle to draw a triangle of any size, where all three angles have the same number of degrees? (Hint: Those three angles should add up to 180 degrees.)
Hamiltonian Cycle
It’s quite fitting that Laurie comes from Hamilton, as her “path back to Hamilton” will be a Hamiltonian path. This type of path, named for mathematician William Hamilton, is a route by which a traveler visits every town on a map exactly once. In this book, I use the word path, but th
ere is actually a slight difference between a Hamiltonian path and a Hamiltonian cycle, which is a path that returns to where it started.