here's one for you math/science nerds:
last night i was watching darren aronofsky's pi, a film i hadn't seen in a few years. if you've never seen it, it has to do with a young mathematician who comes across a mysterious 216 digit number while studying the seemingly random fluctuations of the stock market. he learns that this number is embedded into the very structure of the universe, and that by decoding it, one can predict seemingly chaotic phenomena. for his troubles, he's pursued by jewish mystics and corporate raiders, and much suspense ensues.
anyway, the movie got me thinking about a sort-of real life counterpart to aronofsky's fantasy number, the number omega. omega is a mysterious number that is infinitely long and can never be computed but which does seem to bear some fundamental relationship to the nature of the universe--or at least, those parts of it that concern pure mathematics.
omega is the brainchild of one gregory chaitin, a man who looks more like a mathematician than any other human being who has ever lived. chaitin was intrigued by the work of alan turing, the father of modern computational theory, and kurt godel, an austrian mathematician who more or less wrecked math for all of us back in the early 30s.
what godel did, quite simply, was to show that attempts to contruct some sort of logical and systematic foundation for math was impossible (see russell and whitehead.) godel expressed this in set notation, but an english equivalent that's often given goes something like this:
1. imagine there is an omnipotent machine that is capable of answering any question posed to it.
2. this machine is just a machine, after all, a powerful computer that runs on a program which must be of finite length. you can't write an infinitely long program, of course, and even if you could, you couldn't find a computer to run it in a finite amount of time. this means that the machine will always answer in a finite amount of time.
3. you ask the machine to evaluate whether the following statement is true or false: "you, mr. machine, will never say that this statement is true."
4. the machine ponders. if it says that this is a true statement, then it is, in fact, a false statement since it will have invalidated the statement's only claim. this would be a problem, as the machine is incapable of saying anything false. it decides, therefore, to answer "false," but before it does it realizes that in order to do so, it would then eventually have to say that the statement is true, which takes it right back to square one.
5. the poor machine is done for. it can never answer your question "true," but then, your question was based on the prediction that the machine could never answer your question "true." you walk away feeling quite good about yourself: you were absolutely right all along, knowing something that is true but that an omnipotent machine could never know.
godel's theorem seems like a logician's parlor trick, but it has shocking implications for the fields of mathematics and philosophy. think about it for a second. this machine is omnipotent, it knows every bit of truth that's capable of being known. but even then, there are still truths out there that it can't know. godel has erected an impassible roadblock that boxes humanity's quest for knowledge in. there are statements out there that may be true and that may be false, but as far as we're concerned, they'll simply remain undecided. for a mathematician, this is very bad news. it means that however long or hard he toils, his efforts, however interesting or productive they prove to be, will never approach a comprehensive understanding of the nature of mathematics. he needs to be outside of godel's box to see it, and he can never escape.
a few years later, the british mathematician alan turing applied godel's notion to digital computing--which was no mean feat as the first digital computer would not be invented for another five years.
turing wondered if there was a way for a computer to know in advance whether something was inside or outside of godel's box. imagine you built a computer capable of running any program. we know from godel that there will always be certain problems that are solvable, but which your computer could never figure out, so if you wrote a program that asked it to solve such a problem, your computer would chug away for all time caught in an infinite loop. turing thus set out to find a way to determine if we could know in advance which problems could be solved and which could not, something that's come to be known as the "halting problem."
it works like this. say you want to know what 5 + 5 is but you don't want to burn out a perfectly good computer on an unsolvable problem. so instead of writing a program that would have the computer solve 5 + 5, you instead attempt to come up with a program that asks the computer to tell you instead whether it could solve 5 + 5 in a finite amount of time. how do you do this?
the problem is, a real computer doesn't actually know anything. it's just a calculator. you enter a couple of numbers along with an operator indicating what you want done with them, and the computer does it. it would seem as if the only way to know if your program could run in a finite amount of time would be to feed it into the computer and cross your fingers.
turing found that this is quite correct:
1. suppose there is a program out there called HALT (P,D) that can take some program P, some data to input into that program D, and tells you if P will come to a productive halt or loop on fruitlessly forever when fed data D. for instance, if P were a program that figured out "some number times 5" then D would be the number you wanted multiplied by five, and HALT would tell you if this were doable or not. if it is, HALT will output "halt," and if it isn't, "loop."
2. imagine we told HALT to use P as both the input and the data: HALT (P,P). why would we do this? because it allows us to evaluate whether the program itself will lead to an infinite loop, regardless of what data we use. after all, if P is "some number times five" and what we input is "some number times five" then that's equivalent to asking HALT what happens to P if we multiply any number by five. this will tell us whether P itself is a solvable program, which is just what we're after.
3. "some number times five" is a rather dull program, so let's take a more interesting program called X that simply does the opposite of whatever HALT says. so if HALT says "halt," X loops on forever, and if HALT says "loop," X halts. we then have HALT use X as the input and data, or HALT (X,X).
4. why is X such an interesting program? simple. if HALT (X,X) returns "halt," then the program X will loop on forever, but unfortunately HALT said that it wouldn't, so we have a contradiction. if HALT (X,X) returns "loop," then X will halt, which, again, is exactly the opposite of what HALT said it would do, and again, HALT is contradicted.
5. no matter which way HALT goes, it implies a logical contradiction. but what is the program X? it's simply "do the opposite of whatever HALT says." and if we take X as both our program and our data, HALT (X,X), it becomes "do the opposite of the opposite of whatever HALT says," or, with better grammar, "do what HALT says." in a sense, we've asked HALT to evaluate itself, and what it's determined is that it's bunk. it's self-contradictory. no such program HALT exists.
there the matter remained for quite some time, until the aforementioned gregory chaitin picked up the gauntlet godel and turing had thrown down, which brings us, finally, to omega.
chaitin set out to determine if he could figure out the odds of a program plucked at random from all possible programs halting (or not) when fed into a computer. this probability, he found, was a real number with a value between 0 and 1. he named it "omega." the problem was, although he knew that there was a number out there that could tell you whether or not a program could run--a way to peak outside of godel's box--there was no way to figure out what it was.
why not? the problem with omega, chaitin discovered, was that it was endless and random, much like (as far as we can tell) the digits of the number pi. if you printed it out in binary, it would be an infinite series of 1's and 0's, with each digit bearing absolutely no relation to those that came before. chaitin was able to come up with an equation that, if evaluated, would give you the digits of omega. it worked a bit like the HALT program in that it would tell you, for a given set of data fed into his equation, whether there were a finite or infinite number of solutions. if finite, he could write a 1, and if infinite, a 0. he could thus continue feeding in numbers 1, 2, 3, and so on forever, and get as many digits of omega as he liked.
of course, the equation he created cannot be solved--but he knew that to begin with. after all, by definition, omega was a totally random number where each digit bore no connection to the last, so if there was a formula that could produce it, and that formula could be evaluated, then it would be possible to see some sort of structure in what is absolutely chaotic. after all, you'd simply be applying the same finite set of operations to a series of sequential numbers 1, 2, 3,... over and over again. there would then have to be a connection to the digits of omega since they would have been based on the sequence of counting numbers.
the implications for mathematics are far worse than what godel might have suspected. chaitin's formula for omega was based on number theory, the very foundation of mathematics itself. we're talking about counting, adding, and multiplication here, the most basic, simplest stuff possible. chaitin's formula was based on these operations alone, meaning that the failure to find omega is a sort of a mathematician's uncertainty principle, it's a limit on what we can ever know of number theory, and it's not simply that it's unknowable, it's that, at the core of mathematics, there is deep, deep randomness infused throughout.
what implications might this hold for everyone who isn't a mathematician? some believe that the goal of physics, the so-called theory of everything or TOE, is a fool's errand. physicists are glorified mathematicians, and if math is at its very foundation random and chaotic--a series of disjointed facts bearing no relationship to one another--then there is no reason to believe that such a theory should be possible. some have gone as far as to say that chaitin's work disproves the TOE from the start, but i don't share this bleak assessment. chaitin may have shown we can't know the whole story--in fact, we can know very little of it--but that doesn't mean that what we do know is wrong. there might be enough truth floating around out there within our reach that physicists will be able to somehow manage.
as if the prospect of omega isn't scary enough, chaitin has unleashed greater horrors: super omegas. these come about simply by imagining a machine that could figure out another machine's halting problem, that is, knowing whether or not it could solve a particular problem. it would therefore know omega. however, that machine would have its own halting problem and it's own omega, which could in turn be known by another machine, and so forth.
this hierarchy of omegas actually has applications in computer science. for instance, super omega is the odds of an infinite process producing a finite amount of data, and super-super omega is the odds of an infinite process producing no data at all. some programs are designed to run without halt, like, for example, your computer's operating system, so while it isn't possible to know any of these numbers, if it were, they could have tremendous implications for our modern world--imagine an operating system that never crashed.
so there you have it. omega: a number that allows one to know the unknowable, shows that math is fundamentally chaos, may hold the key to understanding the physical universe, could potentially revolutionize computers and our way of life, which does most definitely exist, and which can never be known.
locdog's brain hurts
locdog movie review: charlie and the chocolate factory
when i was a kid, i had two of my all time favorite movies back to back on a single VHS cassette. the first was predator--and brother, there are two governors whose bad sides you don't want to be on--and the second was willy wonka, mel stuart's 1971 camp classic.
tim burton's updated take on--what? you take umbrage at the term "camp classic" being used on a sacred and cherished part of your childhood? well go watch it again, buster, because you're in for a shock. willy wonka is awful. it's fantastically, deliciously, laughably bad in almost every respect. my favorite moment--besides "burp, charlie, burp!"--is grandpa joe's meltdown in the film's climax: "you're an inhuman monster!"
the only redeeming quality was gene wilder, a lean and mean gene wilder whose reputation as a comic genius was not yet the given it is today, whose glory days with mel brooks still lay ahead of him. his take on wonka was the perfect counterpoint to the film's sugary coating, a hot fudge sunday topped with tobasco sauce. he's an insane, sadistic, melancholy, gleeful, powder keg of energy played played to pitch perfect comic effect time and again--and he's more than a little creepy to boot. wilder's performance in willy wonka is far, far too good for such a rotten movie, and it remains one of my all-time favorites.
by contrast, just about everything in charlie and the chocolate factory is superb--except for johnny depp, who is merely very good.
burton's obsession has ever been finding the humanity in misfits--and one good look at tim burton ought to explain why. in the '71 film, wilder was the lord of his universe, a towering figure that dwarfed all others--it was is if the oompa loompas had to be small since there simply wasn't any other way one could be in relation to the mad genius willy wonka. here, depp is the eternal man-child, rejected by his father, a stern dentist played by a menacing christopher lee, and abused by a society determined to steal his secrets, he withdraws into his own private neverland ranch, where they oompa loompas--decidedly subordinate in the first film--are his only playmates. if we ever need an actor to portray michael jackson, we need look no further than johnny depp.
the most interesting thing about depp's performance for me was his face. you can't take your eyes off of it. he looks like a thirteen year old white girl. he lives in a fantasy land surrounded by little people. he lures children in with candy and golden tickets...ok, i've got to get off this mj thing.
anyway, his face. it's remarkable. half the time i found it difficult to believe i was watching johnny depp, but then he'd twist that china doll face into some wonderfully expressive configuration and that unmistakable talent shone through. gene wilder's turn gave the impression that wonka's manic behavior was just a put-on for the crowd, that the real show was what was going on behind his sardonically-set eyes. depp took the opposite approach, dumping childlike reactions on the screen completely unfiltered. he titters with delight as the oompa loompas go whirling off into another tune, and he matches the petulance of his adolescent guests with ease. when they received in the '71 version, wilder registered boredom, delight, annoyance...anything but concern. depp wisely avoids the same pitfall but not quite as cleanly. there are several crucial reaction shots of him looking on while a child is being thrown into a garbage shoot by rampaging squirrels or turned into a blueberry where he appears to be...well, a little nervous. maybe i'm making unfair comparisons, but i didn't think he was as effective as he could have been. his was a flawed, post-modern willy wonka, a wonka for the new millenium.
i also thought there were instances where burton and depp were laying it on a big thick. the cannibalism line that's running in all the promos fell flat for me. the winks to the tie-dyeds-and-twinkies set (who comprised a considerable portion of my friday night, 9 p.m. viewing) seemed rather obvious. i sensed that burton was trying a bit too hard to be edgy--and it seems to have worked. most of the grownups i've talked to about this film have thought precisely that, that it was edgy. but then, most grownups think that applebee's really is your hometown restaurant because they hang a few jerseys from the local football team on the wall. what made the original edgy--genuinely edgy--was that it was yet another soulless, saccharine kiddy flick which, oh by the way, had an utter madman running loose throughout.
and now i know i'm being unfair. if i wanted the '71 film, i should have popped that old tape into my VCR and watched it. burton's take on the film was exciting and inventive, and if the hip hop hair metal oompa loompas seem a bit plastic to you, then the surprising heart he brings to the main theme of the picture--family--will more than make up for it. i was amazed at how deeply he could make you feel for characters that you've known for decades--there was a twenty-something with a date sitting to my right who actually gasped when charlie ripped open the chocolate bar in the hopes of finding a golden ticket. sure you know he's going to find it sooner or later, but you care about him finding it. in the original film, it was merely a given. and if that original '71 classic was a sappy film with a heart of darkness, today's version is a dark film with a heart of gold.
locdog's next movie review will be stealth--yeah, right