Lauren Ipsum: A Story About Computer Science and Other Improbable Things (16 page)

╞ 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
:

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
).

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:

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
).

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:

This is how Tollens would decide Steganosauruses don’t 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).

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
).

1. Spread the dough into a pan.
   

2. Cover the dough in a layer of pizza sauce.
   

3. Sprinkle cheese on top of the sauce.
   

4. Bake the pizza for 20 minutes at 350 degrees Fahrenheit.
   

5. Take the pizza out of the oven and let it cool.
   

6. Dig in!
   

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 there is actually a slight
difference between a Hamiltonian
path
and a Hamiltonian
cycle
, which is a path that returns to where it started.

On a map with
N
towns, there are (
N
– 1)!
÷ 2 cycles. As Tinker said,
x
! is shorthand for (
x
× (
x
– 1) × . . . × 2 × 1), so for a map with six
towns, you’d have

(6 – 1)! ÷ 2 = 5! ÷ 2 = (5 × 4 × 3 × 2 × 1) ÷ 2 = 60
cycles!

Finding a cycle is fairly easy because there are so many possibilities; finding a
short
one is the hard part! See also
Wandering Salesman
(
Chapter 0
;
Wandering salesman
).

A
Fair Coin
is a coin that has an equal chance of landing with heads or
tails facing up when you flip it. Real coins (like Laurie’s quarters), however, aren’t
always perfectly balanced in weight, so in our world, there is no such thing as a perfectly fair
coin. But for most coins, the odds of landing with either side up are close enough to fifty-fifty
that we have no problem using a coin flip to choose between two options.

Even so, for important things like physics simulations, or choosing who gets to ride in the
front seat, flip twice to guarantee absolute fairness. See also
A Fair Flip
(
Chapter 11
;
Chapter 11: A Fair Exchange
).

When Laurie used the turtle robot to make a circle, she discovered that filling in
one
for
how-big?
made a much bigger circle than she expected. What number
should you plug into
MOTH-CIRCLE
in order to draw a circle two inches in diameter?

No matter which subject you study, there will always be problems that just don’t have a
solution. We say that those problems are
impossible
to solve. Some problems, on
the other hand, can be solved, but only under highly unlikely conditions. Those are
improbable
.

Thank goodness Xor was able to decode Colonel Trapp’s secret message! People have been
encoding information into
ciphers
for others to decode since ancient times, and
today, that science is called
cryptography
. Computers are great at creating and
cracking secret codes, but you can do it, too!

One quick way to encode a message is by using a
substitution cipher
,
which is when you replace each letter in your message with something else. For example, you could
map each letter to a number:

Following these rules, “Hello!” would become “7 4 11 11 14!” But you
can replace those letters with anything you want: different numbers, other letters, or even symbols
you create yourself. Make your own secret message and see if your friends can crack it. Or, share
your cipher with your friends so you can send each other secret messages that no one else can
read!