There were a handful of comic strips from last week which I didn’t already discuss. Two of them inspire me to write about how we know how to do things. That makes a good theme.
Marcus Hamilton and Scott Ketcham’s Dennis the Menace for the 27th gets into deep territory. How does we could count to a million? Maybe some determined soul has actually done it. But it would take the better part of a month. Things improve some if we allow that anything a computing machine can do, a person could do. This seems reasonable enough. It’s heady to imagine that all the computing done to support, say, a game of Roller Coaster Tycoon could be done by one person working alone with a sheet of paper. Anyway, a computer could show counting up to a million, a billion, a trillion, although then we start asking whether anyone’s checked that it hasn’t skipped some numbers. (Don’t laugh. The New York Times print edition includes an issue number, today at 58,258, at the top of the front page. It’s meant to list the number of published daily editions since the paper started. They mis-counted once, in 1898, and nobody noticed until 1999.)
Anyway, allow that. Nobody doubts that, if we put enough time and effort into it, we could count up to any positive whole number, or as they say in the trade, “counting number”. But … there is some largest number that we could possibly count to, even if we put every possible resource and all the time left in the universe to that counting. So how do we know we “could” count to a number bigger than that? What does it mean to say we “could” if the circumstances of the universe are such that we literally could not?
Counting up to a number seems uncontroversial enough. If I wanted to prove it I’d say something like “if we can count to the whole number with value N, then we can count to the whole number with value N + 1 by … going one higher.” And “We can count to the whole number 1”, proving that by enunciating as clearly as I can. The induction follows. Fine enough. That’s a nice little induction proof.
But … what if we needed to do more work? What if we needed to do a lot of work? There is a corner of logic which considers infinitely long proofs, or infinitely long statements. They’re not part of the usual deductive logic that any mathematician knows and relies on. We’re used to, at least in principle, being able to go through and check every step of a proof. If that becomes impossible is that still a proof? It’s not my field, so I feel comfortable not saying what’s right and what’s wrong. But it is one of those lectures in your Mathematical Logic course that leaves you hanging your jaw open.
Zach Weinersmith’s Saturday Morning Breakfast Cereal for the 27th is a joke about algorithms. These are the processes by which we know how to do a thing. Here, Hansel and Gretel are shown using what’s termed a “greedy algorithm” to follow pebbles back home. This kind of thing reflects trying to find an acceptable solution, in this case, finding a path somewhere. What makes it “greedy” is each step. You’re at a pebble. You can see other pebbles nearby. Which one do you go to? Go to some extreme one; in this case, the nearest. It could instead have been the biggest, or the shiniest, the one at the greatest altitude, the one nearest a water source. Doesn’t matter. You choose your summum bonum and, at each step, take the move that maximizes that.
The wicked mother knows something about this sort of algorithm, one that promises merely a solution and not the best solution. And that is that all these solutions can be broken. You can set up a problem that the algorithm can’t solve. Greedy algorithms are particularly vulnerable to this. They’re called “local maximums”. You find the best answer of the ones nearby, but not the best one you possibly could locate.
Why use an algorithm like this, that can be broken so? That’s because we often want to do problems like finding a path through the woods. There are so many possible paths that it’s hard to find one of the acceptable ones. But there are processes that will, typically, find an acceptable answer. Maybe processes that will let us take an acceptable answer and improve it to a good answer. And this is getting into my field.
Actual persons encountering one of these pebble rings would (probably) notice they were caught in a loop. And what they’d do, then, is suspend the greedy rule: instead of going to the nearest pebble they could find, they’d pick something else. Maybe simply the nearest pebble they hadn’t recently visited. Maybe the second-nearest pebble. Maybe they’d give up and strike out in a random direction, trusting they’ll find some more pebbles. This can lead them out of the local maximum they don’t want toward the “global maximum”, the path home, that they do. There’s no reason they can’t get trapped again — this is why the wicked mother made many loops — and no reason they might not get caught in a loop of loops again. Every algorithm like this can get broken by some problem, after all. But sometimes taking the not-the-best steps can lead you to a better solution. That’s the insight at the heart of “Metropolis-Hastings” algorithms, which was my field before I just read comic strips all the time.
Dan Thompson’s Brevity for the 28th is a nice simple anthropomorphic figures joke. It would’ve been a good match for the strips I talked about Sunday. I’m just normally reluctant to sort these comic strips other than by publication date.
And there were some comic strips I didn’t think worth making paragraphs about. Chris Giarrusso’s G-Man Webcomics for the 25th of February mentioned negative numbers and built a joke on the … negative … connotations of that word. (And inaugurates a tag for that comic strip. This fact will certainly come back to baffle me some later day.) Art Sansom and Chip Sansom’s The Born Loser for the 2nd of March has a bad mathematics report card. Tony Rubino and Gary Markstein’s Daddy’s Home for the 2nd has geometry be the subject parents don’t understand. Bill Amend’s FoxTrot Classics for the 2nd has a mathematics-anxiety dream.
And this closes out my mathematics comics for the week. Come Sunday I should have a fresh post with more comics, and I thank you for considering reading that.