## 8/04/2005## 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 ## 8/01/2005## locdog movie review: |