## The Bootstrap Species

Double disclaimer:

1. This is gonna be a rambling rant, as usual.
2. I believe in evolution, not intelligent design. But, part of what’s really cool about evolution is that it creates things that look intelligently designed. It’s therefore very convenient to talk about a species as though it was built to some deity’s specifications. So, I’m gonna make liberal use of that metaphor. Feel free to replace evocative, convenient, and technically incorrect phrases like “We were designed to survive” with the more boring, stilted, and accurate “We naturally happen to be ridiculously good at surviving because if we weren’t better at it than most of our innumerable competitors we wouldn’t exist” if you feel like it.

When I walk into a pharmacy (and, as a typical New Yorker, I buy a remarkable amount of my stuff at pharmacies), I’m often struck by the ridiculous number of things that we have to cure our ailments.

Mostly, it’s a reminder of the amazing variety of ways in which we break: Our bodies crack, leak, buckle, and bleed. Things grow on our bodies and in them. They eat us. Our organs stop functioning or function too quickly or too slowly. We itch. Even our brains–the things that are supposed to be us–often behave in ways that we wish they didn’t. Pharmacies have all sorts of things to cure many of these ailments and to make many more of them more tolerable.

Even stranger, we’re often troubled when things function exactly as they should. Our faces and bodies sprout hair; our nails grow long; sex leads to pregnancy. The pharmacy has solutions to all of these problems too–problems caused by a perfectly healthy body doing what it was designed to do.

There are even solutions to the problems caused by our solutions to other problems.

And, of course, things are pretty awesome as a result. We’ve slowly developed methods (some complicated but many amazingly simple) to tinker with these extremely complex machines that we live in–that we are–to get them to do what we want. We’ve built sprawling pharmacies, and we live long lives with amazing consistency. We’re happier and healthier; we even look better.

But, that is exactly what we’re doing: We’re tinkering with our bodies, and it’s fascinating. We’re now using the most sophisticated machines that we’ve ever encountered to do tasks for which they were never designed. And it’s working! More specifically, we pursue not just survival, not just reproduction, but happiness.

## Measuring the Difficulty of a Question (What Complexity Theory Is)

Suppose you’re given some clear question with a well-defined answer. Computer scientists often like to consider number-theoretic questions, such as “Does 19 divide 1547 evenly?”

It seems quite natural to try to assign to this problem some sort of measure of difficulty. For example, from an intuitive perspective, it’s easier to figure out whether 19 divides 77 than whether it divides 1547. And, figuring out whether two divides 1548 is totally trivial. And, of course, there are much harder problems, like counting all the prime numbers below 1548 .

Some problems’ difficulties take a second to figure out. For example, is it harder to figure out what the square root of 15,129 is or to count the squares less than 15,130? Intuitively, it might seem like the second one should be harder, but really, the answer to the second question is the same as the answer to the first–15,129 is 123^2, and there are 123 squares less than 15,130 (not counting zero), one for each positive integer less than or equal to 123. So the first problem is exactly as difficult as the second.

So, some problems’ difficulties are intuitively comparable. Some are still clearly comparable, but realizing that isn’t completely trivial. But, some problems just seem terribly unrelated. For example, is it easier to count the primes less than 78 or to tell whether 1547 is prime? Is it easier to count the squares less than 123,456 or count the primes less than 78? For questions like these, it seems likely that the actual answers actually depend on our definition of difficulty.

So, we need a rigorous definition of difficulty. The field that studies such definitions and categorizes problems according to their difficulty is called complexity theory, and it’s one of my favorite branches of mathematics. What follows is an NSD-style introduction to the field:

## What’s Cancer?

There’s a nice laymen’s explanation for how most types of diseases work. Viruses, for example, are little pods that inject DNA or RNA into your cells, thus replicating themselves. (Here’s an awesome video by Robert Krulwich and David Bolinsky illustrating how a flu virus works.) Similarly, bacteria, fungi, and various other parasites are independent organisms–made of cells just like us–and its their process of going about their lives inside of us–eating various things (sometimes parts of us), excreting, releasing various chemicals, etc–that makes us sick (or gives us rashes or helps us digest food or boosts our immune system, etc). These various pathogens have evolved to kill. Autoimmune diseases are incredibly complicated (and often poorly understood), but the rough idea is clear: We have cells in our body that are designed to kill off viruses, bacteria, fungi, etc., and sometimes they screw up and kill the good guys instead of the bad guys.

All of those simplified descriptions make perfect sense, and as I’ve become more of a medical nerd, they’ve essentially held up to scrutiny. In other words, they’re good models.

However, the pop-culture description(s) of cancer never really satisfied me. In fact, I would argue that most descriptions of cancer actually ignore the basic question of what the hell this thing is and why it exists. Even my beloved Wikipedia neglects to just come out and say what the damn thing is in its main article about it, though its article on carcinogenesis is pretty good. That type of thing gets on my nerves–I don’t really understand how people can be comfortable talking about something without knowing what it is.

So, until recently, I knew embarrassingly little about cancer. Obviously, I understood that cells mutated and divided rapidly to form cancer, but what made them do that? And why are such a huge variety of things implicated in causing cancer? Radiation, cigarette smoke, HPV, and asbestos are very different things, so how can they all cause the same type of disease? What makes these evil mutant cells so damn deadly? What the hell is metastasis, and why does it happen? I did a decent amount of research and learned some stuff, but I still didn’t really understand what cancer actually is.

That changed thanks to the awesome NPR radio show/podcast Radiolab (which you should absolutely check out if you haven’t already–especially the archives). Their episode on cancer, “Famous Tumors,”finally provided me with a description of cancer that made any sense. It’s still the only decent layman’s explanation of what cancer actually is that I’ve been able to find (and I did a lot of searching while I was writing this blog post up). Once I understood the basics, I found that my other research on the subject actually made sense–even though almost all of it neglected to define the concept in question.

Anyway, you should probably just listen to “Famous Tumors” right now. Seriously. The part that led to my epiphany is a very brief segment that starts around minute eleven or so, and (as is Radiolab’s style), it’s described quite beautifully.

However, for those of you who’d rather read my ramblings, I’ll provide my own description below. In keeping with my tradition of verbosity, this post will take a while to actually mention cancer directly, but I swear the whole thing’s about cancer. Bear with me.

The story starts with a description of what we are:

## A Better Idea than Signature by Squiggle

Like most of you, I sign stuff a lot.

Like many of you, I’m usually a bit embarrassed when I do it. My signature has devolved from a relatively legible cursive “Noah Stephens-Davidowitz” when I was in high school to my college “Noah S-D” to my post-graduation “N S-D” to my current series of four  squiggles, which one might be persuaded are loosely derived from my initials together with a hyphen.

My business partner, Thomas, told me (I think only half-jokingly) that it was unacceptable for signing contracts with our clients. He accused me of just writing the number 900 lazily and sloppily. (I personally think it typically looks more like 907, but that day, I concede, it looked pretty 900ish.) Even people delivering food to my apartment, who only ask for my signature to protect themselves in the unlikely event that I later claim to have not received my food, have asked me to confirm that my signature is in fact a signature.

I would post an image of it for my readership to laugh at, but I suppose that that would be a bit of a security vulnerability.

But, isn’t that incredibly silly? I have in my mental possession four vaguely defined squiggles. For some reason, I’m forced to show people my squiggles all the time as some sort of confirmation that I, Noah Stephens-Davidowitz, am agreeing to something . And, it’s not just with delivery guys; I use my squiggles for extremely important interaction with governments, clients, my bank, etc. But, in spite of the fact that I show this thing all the time, I’m also keenly aware of the fact that posting it publicly on the internet is a terrible idea.

All of this is in case I at some point I say  ”No, I never agreed to that.” Because of my signature, a slick lawyer could then confidently respond “But, if you didn’t agree to that, then why are these four squiggles here? Who but you could have squiggled four times on this piece of paper in such a way?”

Touche, slick lawyer.

## What Color Is

Disclaimer: I sorta figured this stuff out on my own. I did a tiny bit of research for this post, but I’m not very well-read at all on this particular field. So, there’s a decent chance I got something wrong. Oops… Please don’t take what I write here as gospel, and please let me know what I screwed up in the comments.

When I was a kid, I was taught some really confusing and vague things about color. There were the Official Colors of the Rainbow–red, orange, yellow, green, blue, indigo, violet (Roy G. Biv). Three colors were always called primary colors, but there seemed to be disagreement about whether the third one was yellow or green. (Yellow seemed like the obvious choice, though, since green’s just a mixture of blue and yellow. Right? How would you even make yellow from red, green, and blue?) There were various formulas for combining colors together to get other colors when I was painting in art class (E.g., red and green makes brown). But then there were different rules for mixing different colors of light together–like how white light is apparently a mixture of all other colors of light or something. There was also that weird line about why the sky was blue, which seemed to me to be equivalent to “The sky is blue because it’s blue.”

All of this left me very confused, with a lot of unanswered questions: Why isn’t brown a color of the rainbow? Sure, it’s a mixture of other colors, but so are green and orange and purple and whatever the hell indigo is. If orange isn’t a primary color, does that mean that everything that’s orange is really just red and yellow? And why is violet all the way on the other side of the rainbow from red even though it’s just a mixture of red with blue?

At the time, I was too shy to ask because people seemed so incredibly not bothered by all of this. I assumed I must have been missing something obvious.

As it happens, what I was missing isn’t at all obvious, but it’s also pretty easy to explain. (In particular, kids should be taught this.) All of this confusion goes away when you realize what color is and how our eyes and brains measure it. I’ll give a characteristically wordy explanation:

## Light, energy, etc.

A friend and I just accidentally invented a fun game. I like it because it cutely illustrates the current completely ridiculous state of our understanding of human nutrition. Namely, there’s an amazingly long list of things that people think about nutrition–such a long list that it’s just really really hard to imagine even a small fraction of these things actually being true.

(I have a lot more to say about human nutrition than just this. In short, I am extremely skeptical of any claims about human nutrition. I sort of touched on this in this old blog post on my poker blog, and I might do a bit more in the future.)

Anyway, here’s the game:

1. Choose something that people eat that some people think might have effects on your health (e.g. trans fats or calcium or acai berries).
2. Choose a word or phrase that is somehow related to human health (e.g. “asthma” or “concentration” or “bad for you”).
4. Watch as hilarity ensues.

## Is the Universe the Smallest Possible Representation of Itself?

Four centuries ago, Newton showed that the gravitational field of a perfectly spherical object is equivalent to that of a point. In other words, if you pretend that the Earth is spherically symmetric (which is a really good approximation), then, if you want to know the net gravitational effect that comes from this massively complex system made up of about $10^{53}$ elementary particles–each one with its own mass creating its own gravitational field–it suffices to consider the gravitational effect of a single particle. (Admittedly, you need to consider a single particle that weighs 6,000,000,000,000,000,000,000,000 kilograms.) In other words, the gravitational field is simply given by $\frac{k}{r^2}$, where k is a constant and r is the distance from the center of the Earth. (Extending this model to include points within the Earth is easy as well.)

This idea is enormously powerful. It takes a problem that our most powerful computers couldn’t even contemplate and converts it cleanly into a problem that everyone solves as a freshman in high school. Indeed, physicists are so enamored with spherical approximations that they get mocked regularly for it.

So, to act like a caricature of a theoretical physicist for a minute, let’s pretend that the Earth is indeed perfectly spherically symmetric and that it’s the only object in the universe. And, say we only care about gravity in this world. In this fabled universe, it’s not too hard to imagine building a computer that perfectly represents the effects of gravity everywhere in the universe. A user of this computer could enter coordinates and a desired level of accuracy and learn the strength and direction of the gravitational field at those coordinates within the requested level of accuracy. It is even conceivable that this computer could itself be a sphere of uniform density, centered around the center of the earth, so that the computer could easily consider its own gravitational effects as well. (Or, the density of the material from which the computer is constructed at a given distance from the Earth’s center could be the same as all other matter at that distance. E.g., the computer could be as dense as rock and inside the Earth or as dense as air and in the atmosphere.)

## Consequences of the Halting Problem: Gödel’s First Incompleteness Theorem

In my first post on this blog, I defined and proved my favorite fact: The halting problem is undecidable. You should probably read that post if you don’t know what that means, but in brief, it means that it is impossible to write a computer program that will always correctly tell you whether any given computer program will run forever or eventually stop.

I promised to talk about some of the far-reaching consequences of this fact in future posts, and here I am keeping my promise, if a little late. (Don’t get used to me keeping my promises on this blog, though…) I’ll start with arguably the biggest consequence of the halting problem’s undecidability: Gödel’s First Incompleteness Theorem.

As is my m.o., I’ll try to keep the discussion accessible to laypeople; I’ll provide lots of context; and I’ll just generally be extremely long-winded.

This post will be even more long-winded than usual because I feel the need to provide way too much context. To sort of acknowledge that this post is absurdly long, I’ve put a little (*) in the heading of sections that are less tangential. I’m incredibly biased, of course, but I suggest attempting to make it through the whole thing, and if you get tired somewhere around Euclid or Cantor, skip ahead to the next asterisk.

## A Simple Vulnerability Found in… Lots of Stuff

(Since this blog is read by a lot of poker players, it’s probably a good idea to mention right away that I don’t know of any way that this vulnerability could affect poker client software.)

My friend Thomas Bakker recently showed me an amazing (and hour-long) video from the recent Chaos Communication Congress, which is essentially a conference in which various hackers get together and laugh at the current state of computer security implementations. These types of things are very helpful for people trying to improve security, but of course, they’re also absolutely terrifying. Most of the scary stuff discusses specific vulnerabilities that are unique to a device or piece of software. (Here, for example, is a short video showing a man-in-the-middle attack that works against every iPhone 3G.)

Those things are freaky enough. However, Alexander Klink and Julian Wälde (a penetration tester and a student respectively) demonstrated a much much more general attack. Instead of targeting the specific security implementations of one particular piece of software or device, their attack targets the programming languages that almost all major websites use: PHP, Java, ASP.NET, and Python amongst others. Basically every modern website on the internet uses these, including, for example, Facebook, Twitter, Two Plus Two, Subject: Poker, the New York Times website, YouTube, this blog, Wikipedia, Gmail, whitehouse.gov, and cia.gov.
(more…)

## My Favorite Fact: The Halting Problem

I figure the first topic on my blog should be my favorite. It concerns a question that is fundamental to computer science theory called the halting problem. It’s really not a fact about computers or computer programs at all; it’s just best formulated in that way. It was first solved in 1936 by Alan Turing, and one can argue that the basic question goes back at least to David Hilbert’s 23 problems in 1900 (although Hilbert initially assumed something that was false in his question). It was introduced to me by Professor Eugene Charniak a few years ago in his class on models of computation, and it’s a relatively standard problem that undergrads in computer science learn about at some point.

Most importantly, it’s really beautiful.

I’ll introduce the problem and prove the solution in this post. In a future post, I’ll discuss the wide-ranging consequences.