5 Things I learned in 2015 from a year of blogging about a book

About a year ago, for some misguided reason, I decided it would be a good idea to blog my way through a big book called Gödel, Escher, Bach, one post per week for all of 2015. Since this time of year is rife with retrospective listicles  (I recommend Chewychunks‘), here’s my humble contribution.

1.) The book was more digestible than I was expecting – Sure, there were some parts that were tough to get through, but, on balance, Hofstader’s writing is lucid and quirky. GEB is as much a study in the clear articulation of abstract ideas as it is about computing and consciousness.

2.) The Seinfeld Technique works – So does the commitment device of public self-induced shame. A few posts may have been short and lame, but I managed to get something, anything, up by 11:59PM every Saturday. Hofstader’s Achilles says it best: “It’s a strict regimen, but it pays off.”

3.) Art is weird and that’s ok. In another unexpected turn, some of my favorite posts to write turned out to fall under the “Escher” category. I’ve found myself rewatching the videos featured in “My Kid Could Do That” and “Metaphysics of Notation“.  They’ve changed how I think about places like the Hirschorn

4.) Quaerendo Invenietis – Hofstader invokes this latin aphorism in his initial description of Bach’s Musical Offering, two movements of which use the phrase as a subtitle. The translation:”Seek and ye shall find”. It turned into a nice slogan for this project, which I’d originally thought of as mapping closely to the book itself. Instead, I ran out of book material about halfway through, and found myself in DeepDream, the Robot Apocalypse, and that stupid dress.

5.) There is (almost) always another level – Gödelian paradoxes aside, truly rare is the situation that can’t be stepped back from and considered from a wider perspective.  Hofstadter only concretely mentions this a few times, but it’s a pervasive theme that keeps sneaking back into both his dialogs and prose throughout the whole work. His gentle reminders in the book have made it easier for me to remember to do this outside the book.  It’s vastly improved my year.

Now what? With one year fully complete, I won’t be continuing the non-negotiable weekly posting schedule in 2016.  I will leave the site up and continue to add new content if it seems timely.

And that’s it.  I wish there was a profound conclusion to conveniently wrap this all up, but I don’t have one. Even if I did, it’s probably most for a project inspired by Strange Loops to end more messily.  The best I can do is to let Achilles say it for me.

“I don’t mind admitting that, as I pondered the idea, my thoughts got more and more tangled, and in the end I really didn’t know what I thought. But this idea…it boggles the mind.”

Advertisements

Calvin, Hobbes, and Markov

I’ve long been a fan of Garfield Minus Garfield, a web comic created by Dan Walsh in which he takes Jim Davis’ original Garfield cartoons and photoshops out all evidence of the famous orange cat.  The remaining result reveals, “the existential angst of a certain young Mr. Jon Arbuckle. It is a journey deep into the mind of an isolated young everyman as he fights a losing battle against loneliness and depression in a quiet American suburb”.

It’s brilliant. And it gets dark, quickly.

This week, I discovered Garfield Minus Garfield’s spiritual successor: Josh Millard’s Calvin and Markov

These surreal reconstructions of one of the most universally loved cartoons ever come to us courtesy of…math?

Both Garfield Minus Garfield and Calvin and Markov don’t contain any new content themselves.  Instead, they run the original strips through an algorithm to generate the new ones.  Garfield’s algorithm is pretty simple (Step 1: Remove Garfield, Step 2: Laugh at Jon’s pain), but Calvin’s is a bit more interesting.

Millard uses a structure called a “Markov Chain” to create his bizarre Calvin strips. Markov chains are the result of a process that depends only on the state that it is currently in, while any past or future state is ignored. Lots of board games are based on Markov chains, where the actions that you can take on a given turn depend only on the particular square that your piece is currently on.  Nothing that happened on a previous turn can affect the possibilities for what can happen on your current turn. If you’re playing Monopoly and you’re on Mediterranian Ave., there’s no way you can roll the dice and land on Boardwalk, even if on your last turn you were sitting on Park Place. Your current position is the only information that can define what happens next.

Millard has an excellent blog post describing the details of how he applies this same logic to Calvin and Hobbes, but the basic idea is, like Garfield, a simple algorithm.  First, like most interesting data problems, there’s a lengthy data cleaning step where the raw comics and their associated text are cataloged in a format that is easy for the computer to analyze. Next comes the actual algorithm, which decides which piece of text to insert into a given speech bubble based only on the last blob of text that was inserted and the character who’s going to be speaking the new line (Calvin’s lines remain his, same with Hobbes’).

The final result is a testament to the weirdness of mathematical randomness.

Go, Go, Gadget…Go!

I did something dumb. I started learning how to play Go.

Like most stupid mistakes, I had good intentions.  I figured it would be an appropriately Hofstadterian exercise to learn the game that’s become synonymous with structures so complex that computers struggle to make sense of them. Unfortunately, Go turned out to be a fantastic distraction from work and school.  The game wins again…

I won’t get too deep into the rules here, because there are much better explanations posted elsewhere. The gist of the game, though, is one of capturing territory by placing pieces on a 19×19 grid.  For someone like me just getting used to the rules of the road, this full-size board is a bit like putting someone with a learners permit into a Porsche.  They might hack it for a few miles, but eventually they’ll crash and burn.  With that in mind, I’ve been playing with the Go equivalent of a golf cart – a 9×9 board.  Not only does this keep things simpler, it also makes games faster.  Fast iteration becomes really important when trying to adhere to the famous proverb, “Lose your first 50 games of Go as quickly as possible”.  I’m really good at losing so far.

What makes my robust string of defeats even more embarrassing is that I’m playing against an opponent who is notoriously bad at Go: a computer. By comparison, computers are excellent at Checkers. There are “only” about 5*10^20 possible outcomes in a game of Checkers.  This is a big number (five hundred billion billion), but it’s a doable task for a computer to keep track of every possible move in a given game and calculate the best one. Chess, on the other hand, has about 10^120 possible moves. A computer will have a much tougher time dealing with such a huge list of possibilities, which is partially why Deep Blue’s defeat of Garry Kasparov was such an achievement (Radiolab did a great story about this). For Go, it’s not even close.  On a full-size board, there are over 10^761 possible games.  There’s no brute-forcing possible here.

If a computer is going to be able to “solve” Go (beat real players, not losers like me), it’s going to need to try something else. Enter Machine Learning. Instead of keeping track of every possible move, researchers are instead trying to build models that interpret Go positions using the same process used for image classification (the one that, when abused, led us to DeepDream).  The idea is that this approach will enable computers to “think” about Go more like humans do, where players make moves based as much on “intuition” as they do concrete plans about the next set of moves. Naturally, this has now let to a Silicon Valley arms race, where Facebook and Google are competing to see whose computer army can defeat the Go masters first.

In the meantime, they won’t have to worry about building a computer that can beat me.  This one is already great at it.

Making the difficult easy

Looking for some interesting holiday viewing?  Check out Traveling Salesman:

Finding a coin in a beach made of glass? Unlocking a new dimension? A guy with his head in a C-clamp? Looks pretty great, but what is this movie actually about?

In short, it’s about what happens if you discover that hard problems and easy problems are really all the same.  In math and computer science, this is described as P vs NP, and it’s one of the biggest unsolved questions out there.  So big that that there’s a $1,000,000 bounty out there for anyone who’s able to solve it. Oh, and the first person to pose the question back in 1956? That would be Kurt Gödel.

Let’s call the set of problems that are easy for a computer to solve, like sorting a list of numbers “P” type problems. In contrast, we’ll call the set of problems that are hard for computers to solve but easy for them to check if a given answer is correct “NP” type problems.  Finding the shortest route between a set of cities that never repeats and visits each city only once, the “Traveling Salesman” problem, is NP problem.  It would take a computer zillions of cycles to test all the possibilities, but if you gave a computer two routes to compare, it could very easily tell you which was the shortest.

The big question is whether or not there is some fundamental difference between P problems and NP problems. Sometimes we’ve made some progress on solving NP problems that seems to suggest they might be easier to solve than we think (like graph isomorphism), but no one has been able to do this reliably yet.  In the end, we still don’t really know. The debate has continued to rage, even spilling over into pop culture.

Or, at least, pop culture created by Matt Groening

Once again, the internet does a great job of providing an overview on the whole mess:

Back to the film: Traveling Salesman simply present a vision of what might happen if someone were to prove that P=NP.  It gets pretty wild pretty fast.  I won’t give away any spoilers, but instead will just mention that its available on Amazon Prime for your next nerdy movie night.