Wall? What Wall?

The excellent Mike Lee (@bmf on twitter) has a hilarious way of handling theoretical problems: he ignores them to solve them.

In a case of life imitating art imitating life, programmer Mike Lee explained his writing a solution to the halting problem, with the simple explanation that, lacking a formal education in computer science, he didn’t realize it was considered unsolvable.

To solve the halting problem is to write a function that takes any function—including itself—to determine whether it will run forever, or eventually stop.

The classical approach is to wait and see if the function halts, but the necessity to accept itself as input means it will end up waiting for itself.

This paradox is what makes the problem unsolvable, but Lee’s function avoids the paradox by using a different approach entirely.

“It simply returns true,” Lee explained. “Of course it halts. Everything halts. No computer is a perpetual motion machine.”

That being said, the scientists vs engineers problem is an old one. Computer science started out as a branch of mathematics, and was treated as such for the longest time. When I was in college, we didn’t have any exam on an actual machine. It was all pen and paper!

Part of the problem of any major “it can’t be done” block on the road is the sacrosanct “it’s never been done before” or “such and such guys have said it can’t be done”. The truth, though, is that technology and knowledge make giant leaps forward these days, mostly because of people like Mike who just want to get things done.

Just remember that a few decades ago, multi-threading was science fiction. Nowadays, any programmer worth their salt can have a builtin “hang detector” to monitor if a part of their program is stuck in an infinite loop, or has exited abnormally. Hell, it’s hard to even buy a single-core machine!

I distinctly remember sitting in a theoretical computer science class, listening to a lesson on Gödel’s numbers. To oversimplify what I was hearing, the theorem was about how any program could be represented by a single number, however long. And about 5 minutes in, I was saying in my head “duh, it’s called compiling the program”. Had I said that out loud though, I’d probably have gotten in a lot of trouble.

Don’t get me wrong though, I think that mathematical analysis of computer programs is important and worthwhile. I’d like to be able to talk about optimization to a whole lot more people (how you just don’t use an O(n³) sorting algorithm, please…). But whereas I see it as a valuable tool to prove something positive, I stop listening whenever something is deemed impossible.

Trust Mike (and to a lesser extent me) on this: if something is impossible, it’s probably because the right tools haven’t been used yet. Maybe they don’t exist. And I’m ready to acknowledge that there is a probability they won’t exist any time soon. But “never” is a long time for anything to (not) happen.

UPDATE: it seems that people link it with the skeuomorphism ranting from before. True, it does ring familiar: we do things like we’ve always done, because we can’t do otherwise. Right?