Saturday, September 10, 2011

science is compensation for smallness

The same essay I was just talking about also has this great paragraph stuck in towards the end, fairly separate from the rest of it:
Indeed, one could define science as reason’s attempt to compensate for our inability to perceive big numbers. If we could run at 280,000,000 meters per second, there’d be no need for a special theory of relativity: it’d be obvious to everyone that the faster we go, the heavier and squatter we get, and the faster time elapses in the rest of the world. If we could live for 70,000,000 years, there’d be no theory of evolution, and certainly no creationism: we could watch speciation and adaptation with our eyes, instead of painstakingly reconstructing events from fossils and DNA. If we could bake bread at 20,000,000 degrees Kelvin, nuclear fusion would be not the esoteric domain of physicists but ordinary household knowledge. But we can’t do any of these things, and so we have science, to deduce about the gargantuan what we, with our infinitesimal faculties, will never sense. If people fear big numbers, is it any wonder that they fear science as well and turn for solace to the comforting smallness of mysticism?
Isn't that great? The same thing applies in the social sciences, even though these by definition study things that are on human scales. If we could live for millennia and hold terabytes of information in our minds easily, we could simply see the phenomena we hope to deduce through the social scientific method. Just like we don't need studies to tell us that smiling at people makes them happy, or paying more on rent than you earn will land you broke, we wouldn't need studies or statistics to sort out the subtle interactions between education and social norms and property rights and social preferences (to take a random example...)

Although, I think it'd be a stretch to describe mathematics or engineering in this way. Mathematics doesn't concretely exist in the world; we invent or choose axioms and then discover what truths they imply, and those truths frequently tell us something about the real world, but they don't exist to be observed until after they're created/discovered by mathematicians. Likewise, engineering. When I say engineering I don't mean studying the world with the aim of using that knowledge to build things (that's just science, and the above applies), but building things and studying what we build. Then, once again, the object of study doesn't exist until we create it (whether it's the effect of nuclear waste disposal or of the design of government institutions) and we can't, with large enough brains and enough time, just look at the world and know the answers.

Science vs. anthroposcience? Science vs. quantitative 'art'? I'm not sure how to define that latter category exactly. But you see what I mean.

Tuesday, September 6, 2011

computability and big numbers

I recently realized (through finding a computer version of trivial pursuit, which provides player statistics) that I'm a little less terrible at the geography category than the science category. The resulting minor identity crisis put me on a bit of a science kick, which included reading this great essay a friend of mine sent me (thank you Kenny!) that I can't believe I've never seen before. Read the whole thing if you like numbers or computation in the least. In particular, the relation between computability and big numbers is fun. The idea goes like this:
  • Consider a computer and all the possible programs we could write for this computer (intuitively, don't think of interactive software programs, think of a program you start running, and then you wait, and then it eventually gives you an `answer'. Like a calculator.) Specifically, consider a Turing machine.
  • Computer programs can be written to compute whatever you want them to. The problem is, it's hard to know if it will finish computing that thing in finite time. It might get stuck in an infinite loop, counting all the way to infinity looking for something that doesn't exist. The halting problem is: can I examine an arbitrary program and decide whether or not it will terminate in finite time?
  • It turns out that it is not possible to write a computer program that solves the halting problem. The proof is great but repeating it would take too much length and specificity, so just read at that link.
    • But since I can't resist, it basically goes: Say h(i,j) is an algorithm that returns 1 if program i terminates on input j, 0 otherwise. Then define g(i) to be 0 if h(i,i) is 0, and to loop forever if h(i,i)=1. But then either g(g)=h(g,g)=0, or g(g) doesn't terminate and h(g,g)=1. Either way, you have a contradiction with the definition of h. As Aaronson puts it, "Like a hound that finally catches its tail and devours itself, the mythical machine vanishes in a fury of contradiction. (That’s the sort of thing you don’t say in a research paper.)" *grin*
  • Any program is defined with a certain exact number of rules. Think about all the possible programs that contain exactly N rules. There are only finitely many of these programs, since N is finite and there are only finitely many possible types of rules, so we can hypothetically make a list of all of these programs.
  • Now consider what happens when you run each of these programs. Some might terminate and some might loop forever, but among the ones that terminate, one of them takes the longest. So, you can define BB(N) to be the length of time that the longest-running program with N rules takes (that is, the Nth Busy Beaver number.)
  • Can a Turing machine compute these numbers? If it could, it could solve the halting problem by simply watching a program with N rules run for BB(N) steps, and if it hasn't finished by then, by definition of BB(N), it never will. Therefore, the BB number sequence grows too fast to be computable, because we already know that the halting problem isn't computable.
  • Even more striking, BB(N) grows faster than any computable sequence: Say there is some number sequence that is always greater than BB, D(N)>BB(N). Then if we can compute D(N), we can automatically compute BB(N), because we just run every N-rule program, and among those that stop within D steps, the longest-running one takes BB(N) steps. Therefore D doesn't exist.
    • One minor addendum to that: even if we don't know that D is greater than BB, or even if it was somehow not possible to know for sure, having computational access to D allows us to unknowingly calculate BB, which is in principle not possible.)
  • So in summary: the BB number sequence is really, really big. So big, no computer can possibly keep up when trying to calculate them. And this connection between computability theory and big numbers is cool :)
A side note about amateur interests: isn't it nice learning this stuff in bite-sized chunks instead of in five-minute flurries in math classes that are so dense with mulling-requiring ideas that you can never catch up enough to enjoy how beautiful it is? Sure, at this rate I couldn't never learn enough to be a theoretical computer scientist, but what's the point if it's not enjoyable? Not to say it's not possible to learn enough or work hard enough where that pace would be enjoyable, but I already picked a different niche specialize in, and I don't want to completely lose touch with science just because I can't devote so much time to it.