Slashdot Mirror
Metamath! The Quest for Omega
Chaitin's goal is the casual reader's comprehension of an irreducible, uncomputable, and truly random real number. He doesn't actually find one of these numbers, of which there are an indenumerably infinite supply, but he comes as close as a person can to actually referring to it.
Does this sound mysterious (and a little weird)? It is! But this ties in to just the sort of problem mathematicians have been working on for the past hundred or so years. You may be familiar with Goedel's Incompleteness Theorem, in which he proves that no formal axiomatic system (FAS) is powerful enough to prove all of the true statements its notation can express. For a long time, many people were wondering if Fermat's Last Theorem could be one of these statements (although it was finally (and famously) proven by Andrew Wiles about a decade ago). This is the type of "metamathematical" problem Chaitin attacks with his arsenal of complexity and information theory.
Key to understanding the book's premise is understanding the problems involved in defining a truly random number. Chaitin works in binary, so it is easy to find a random number by flipping a coin multiple times, although defining what a random number is supposed to look like (without circularly using the word 'random') is impossible. If you can define exactly what it should look like, then you can use that definition to create (or compress (see below)) a random number. It would not, then, be random.
The next key word is 'reducibility' (or 'compressibility'). If a number is random then it cannot be reduced or compressed into a smaller equation or algorithm. The digits of pi appear to be random, but they are reducible. This entire infinitely long real number can be expressed with just a few symbols- 4*sum_(k=1)^n(((-1)^(k+1))/(2k-1)). The same is true with 'e' or the golden ratio. You might be aware of the distinction between denumerable and nondenumberable infinities-- Chaitin explains this in his book; in short, there are (at least) two kinds of infinite sets, those that map directly to the integers (e.g. the rationals) and those that don't (e.g. the reals). It has been shown that all computer programs may be mapped to integers and hence are denumerable. Any number that can be generated by a computer program (pi, e, etc) therefore is denumerable. For Chaitin's random real number to be truly random, we must look only at real numbers that are indenumerable (cannot be calculated-- otherwise it would be compressible).
Here is where we run into problems-- we can't possibly generate a random real number and we can't even define what it looks like! Chaitin discusses the philosophical arguments for the very existence of such a number, and in the end uses Turing's Halting Program idea to show that a random real number can exist-- and the random real number vaguely referenced in this way, he calls Omega, the halting probability. The probability that an arbitrary program halts is the random real number that Chaitin had been searching for.
But this is not giving away the ending by any means. In fact he tells us this before even embarking upon his journey. What is remarkable about the book is that, in plain English, and using ideas that a non-mathematician like myself can understand, in only 157 pages, Chaitin can explain the grandest ideas on the cutting edge of mathematics. "As you have no doubt noticed," began Chaitin's conclusion, "this is really a book on philosophy, not just a math book. And as Leibniz says... math and philosophy are inseparable."
Although the book can be read quickly and painlessly (there are only a few simple equations in the book), the insights it contains are profound and likely to stick in your brain for some time. Furthermore Chaitin's enthusiastic style is contagious and will leave you on the edge of your seat. He floats through dozens of interesting anecdotes about the great mathematicians-- Leibniz, Newton, Turing, Godel and others--, the process of mathematical discovery from the vantage-point of an actual mathematician, insights into the mind of a working mathematician, and the craft of mathematics, interjecting his own educated thoughts on all of these matters. His style is aimed towards those whose education in mathematics extends only a little past high school and the ideas are simply followed (don't worry if you can't follow my own explanations above; I'm not nearly as skilled an expositer as Chaitin!)
This book is available for free on Chaitin's own website (so why not give it a try?) and also at ArXiv.org. Slashdot welcomes readers' book reviews -- to see your own review here, carefully read the book review guidelines, then visit the submission page.
That sounds pretty cool, but I barely made it through geometry. This would destroy me.
If this book is reflective of the way I meta-moderate, it should be a breeze!
Hmmm.
Trinity dies while trying to rescue Alan Turing from Zuse's mind control device
Math heart racing? Only on exams
Interesting math books remind me of a book I read a few years ago. Zero: The Biography of a Dangerous Idea by Charles Seife. As fun and interesting as I found math to be, I think that book really did it for me as far as spine tingling mathematics.
Worse still is calling it a "mathematical-bodice-ripper"
All props to the author and review...but this one isn't going to be an up all night page turner for me.
When the people fear their government, there is tyranny; when the government fears the people, there is liberty.
Have you ever read a math book that was able to carry you through its proofs, heart racing, and make your skin tingle upon reaching its philosophically astounding conclusion?
I can honestly answer this question: no
Which actually states that any sufficiently powerful formal system can express true propositions which cannot be proven. Typically, "sufficiently powerful" means self-referential to some degree; the system must be able to refer to a propostion within it, and the truth/falsehood of that proposition.
I am not a mathematician, though, so this may not be completely accurate. However, I am fairly sure that it is not difficult to compose a formal system which is provably complete.
I remember your eyes, on the twelfth of July...
now he needs to release it under the new paradigm :)
of academic textbooks.
like the MIT heat transfer book
i kind of like this idea, that if something was
important enough for you to write down for humanity,
you are just doing it for the sake of society.
that would probably take a huge cut out of the
whole "i wrote a book now buy it for my class"
effect...
I realize it takes a while to write a book, but doesn't it usually need to be finished before someone can read and review it? If it is already finished, why is it taking so long to publish it? Surely it can't take a whole year to setup the press to print the book.
Edward Burr
Having a smoking section in a restaurant is like having a peeing section in a swimming pool.
Fermat's Enigma: The Epic Quest to Solve the World's Greatest Mathematical Problem is one of those other really really exciting mathematics books.
Comment removed based on user account deletion
"The probability that an arbitrary program halts is the random real number that Chaitin had been searching for."
Perhaps the Slashdotting his ~300KB ebook is about to receive would be a good case study...
[Scene: two children on a playground playing cops+robbers]
Chaitin: I got you!
Milhouse: I got you twice!
Chaitin: I got you [thinks very very fast] Omega!
Milhouse: I got you (Omega + 1)!
Chaitin: AAAARGH!!!
Fin
I want to drag this out as long as possible. Bring me my protractor.
Slashdot, what were you thinking?! I was under the impression that only high ranking Starfleet officials were to be told of Omega, yet you go posting a review of it on the front page!
*Publisher not responsible for any mental or physical anguish caused by this book.
I Am My Own Worst Enemy
i think they should create another version of the book...
'Metamath! The Quest for Omega For Dummies'
Comment removed based on user account deletion
He doesn't actually find one of these numbers, of which there are an indenumerably infinite supply...
What the heck does that mean?
--
As a matter of fact, I am a lawyer. But I play an actor on TV.
I've been outnerded.
Man, I thought I was a dork, but I stand humbled in the presence of a math book reviewer. I thought my star trek fanzine and degree in robotics had me prepared, but in one swift book review, all my nerdly accomplishments are like ashes in the wind.
Best Windows Freeware
...Chaitin tell you his own work is the most important work in mathematics? If he does it less than 100 times in the book I may consider reading it.
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
Nerds are nerdy. They, like, care about how stuff works.
There are many math-loving nerds.
Why did falcon5768's dumbass response gets moderated up? It should have plummeted to -1 immediately. It's obvious. It's not insightful. It's not put cleverly. It's boring. It's dull.
He's like one of those pitiful kids at a math convention trying to act cool by talking about how at math convention he could see how dorky everyone was.
What a fucking toolshed!
I don't think that the continuum hypothesis is "believed to be true". I seem to remember reading about someone proving that it is unprovable within the normal system of axioms. Which means that not only nobody knows if it's true, but it is impossible to know if it is true. You can arbitrarily decide one way or the other, though.
I was reading a book called "Information and randomness" the other day (highly technical book) and about 50 of the papers in the bibliography are by Chaitin! Seeing how often Chaitin's theorems/discoveries etc. are cited made me realize how vast this guy's contributions are. People so deeply involved in research rarely write popular math books, and so its a pleasant surprise to see that he does, and is quite good at it.
It is rarely so technical as to terrify and his sense of humor and careful exposition makes reading his stuff enlightening and fun all at once.
Highly recommended.
Comment removed based on user account deletion
is somebody going to need to understand the book? Unfortunately for myself I was not born with the genius gene, and being in highschool (just finished sophmore year, taking alg3 next year), I don't understand a lot of the more advanced pyshics and math discussed on /.
It has been shown that all computer programs may be mapped to integers and hence are denumerable. Any number that can be generated by a computer program (pi, e, etc) therefore is denumerable.
Even if the writer's conclusion is true, it is not so obvious as to justify stating it without argument.
Those who would give up essential liberty to purchase a little temporary safety, deserve neither liberty nor safety.
He mentions that the book is about defining true random numbers. Now then, this suggests that randomness is a matter of degree, that is, some numbers are more random than others. I suppose the best way to determine the most random number is to poll people to pick a random number and see what the most common choice is.
Unknown host pong.
I'm too lazy to look up which mathematician/physicist said this:
"There are only two kinds of math books: those you can't read past the first page, and those you can't read past the first sentence."
Anyway, Chaitin's other books are really interesting too. There is one called "The Limits of Mathematics" which discusses Godel's proof and even "shows" it interactively with some LISP code at the end. The whole book is free online here, which is a great deal for a very interesting Springer text. Some people think Chaitin too arrogant, but there's not denying he's a great mind.
You are a bigger dork. You complained about it and tried to act cooler than somebody else when it is clear that you are not.
"I'm not a nerd. Nerds are smart."
Comment removed based on user account deletion
Any number that can be generated by a computer program (pi, e, etc) therefore is denumerable.
That's only correct in the sense that no infinite processing is considered. Pi is irrational and as such is not denumerable (rational).
What's in a sig?
What's in a sig?
FYI, the continuum hypothesis is neither true nor false (or BOTH true and false, depending on how you think about it :).
It is independent of the rest of set theory... much like Euclid's parallel postulate is to geometry. You can assume it's true, or assume it's false, and you get different versions of set theory in the end. Similar to the existence of both euclidean and non-euclidean geometries.
Many people don't realize that there are multiple versions of something as fundamental to mathematics as set theory! Check out the Axiom of Choice for another example of something that's neither true nor false in set theory.
My favorite proof involving cardinality and set theory is the proof that there are the same number of integers as fractions... so simple that a school kid can understand every step, yet so profound a conclusion!
DiscDividers tabbed plastic CD dividers: divider cards f
Comment removed based on user account deletion
We spent about half a semester going from Maxwell's equations to the thin lens approximation.
In a mathematically contiguous manner--no hand waving arguments, all solid derivations and proofs.
With lab.
From electromagnetic theory through to everyday optics. It was fucking beautiful.
Well, I have to go now. I have a date. With my wife.
Nope. Still pegged.
"Reality is that which, when you stop believing in it, it doesn't go away." - Philip K. Dick
There are a number of reasons to disbelieve the continuum hypothesis. Probably the largest reason is that the Continuum Hypothesis is a minimizing assumption: it explicitly rules out some kinds of sets that might be interesting to study.
h tm l has a round-up on perspectives to this.
http://mathforum.org/library/drmath/view/51437.
When you first meet the various types of infinities, it's not too much of a stretch to believe the continuum hypothesis -- however, as you get further and futher into the study (incorporating things like 0#, V = L, and so on), it becomes clear that the constructible universe L (in which CH is true) is a very small and restrictive universe of set theory that does not describe all of ZFC.
Even if CH is "true", it's a very weak statement that is either refuted or a corollary of more interesting statements that say more about the entire universes of sets, rather than of two cardinalities. It's even actually possible to construct models of set theory where the powerset of one infinite set has the same cardinality of any strictly greater infinite set.
Just to comment on a sentence in the review, Chaitan's number isn't on the cutting edge of mathematical logic... the idea that there's a non-computable real is as old as Turing and the Halting Problem.
I have made a beautiful proof that omega > 0.42
but this comment is to small to hold it.
Knud Sørensen
Man, I thought I was a dork
:)
Well, not to pussyfoot around the issue, you are by virtue of having a Trek fanzine. Any dork can have a Trek fanzine, even one without a degree in robotics, or a brain.
Math is about geekyness, not dorkyness.
But hey, if you weren't such a dork you'd already know that.
KFG
Hmmmm ! I don't know about maths or geometry but some of the best kicks I got was from a book called "The Cosmological Argument from Plato to Liebniz" by William Craig Lane. In particular the chapter on Don Scotus' form of the argument was a logical tour de force. Really blew my mind. Of course these arguments are proofs not demonstrations so if you like logical forms with a theological bent check this out its last imprint was 2001.
Counterexamples to the continuum hypothesis abound from stronger axioms than ZFC. ZFC is not strong enough to really say anything about higher infinities (except for some very basic facts about the cardinalities of powersets, singular/regular cardinals, and so on).
However, the above logic to argue the 'truth' of CH isn't correct. Within ZFC (which CH is independent from), you can also formalize the statement X: "2^aleph_0 = aleph_2". This statement can never be proved/disproved from ZFC. X and CH are clearly incompatible -- that is, only one of them can be true. You'll never be able to find a counterexample to X, so by your reasoning, it must be true!
The moral is that you have to be very careful when dealing with infinities and higher set theory. Unprovable things that may seeem intuitively true are only 'true' from your perspective and universes exist with these intuitively true things false.
Right. That's why the reviewer says "there are (at least) two kinds of infinite sets". Infinity is, I suppose, somewhat more than two, no matter which infinity you choose. But you can do a lot of interesting stuff with just the two he mentions.
Actually, if this book is compelling, I hope that some of the academic book authors take an example and figure out a way to make math interesting and compelling for children to learn in schools. It is a real shame that most of the public school system in the U.S. makes math seem so boring (the memorization of formulas and crap, rather than learning something that is truly useful and learning how to apply concepts to solve real life problems) that most kids do poorly in math. This, in my opinion, is part of the reason that a lot of the programmers being turned out by schools suck, but think they're hot stuff because they can turn out word processors with VB#.NET or whatever. They really don't have a good solid foundation in math, logic, and science to make really good software. The same problem applies to other areas as well, which is why a lot of U.S. jobs are being outsourced to other countries. I strongly believe that if the public education system here in the U.S. were improved drastically, a lot of employers would see a compelling reason to pay the higher price for domestic workers, because they would get increased value out of their investment.
Anyway, that was a rant, but I think a lot of technical subjects, like math, tie into the greater overall problem of teaching children how to think, how to apply concepts, how to learn something when they don't know the answer, rather than how to memorize the steps to accomplish a particular task, and fail when the task doesn't exactly match, they fail...
There are only so many properties of real numbers that we can actually describe in words. (Same number as the cardinality of N.) Most of these properties are either almost always true (i.e. the set of numbers for which it's not true is not dense in R) or almost always false. A random number is one that is on the "almost always" side for each of these properties; i.e. transcendental, normal, non-computable, etc.
An interesting take on these incompleteness theories is Jaakko Hintikka's book "The Principles of Mathematics Revisited." He states, among other things, that Gödel only proved the deductive incompleteness of Arithmetics, but his result is really not that important as it says nothing about the descriptive completeness of systems. His (Hintikka's) point is, that deductive completeness (the possibility to deduce all the possible sentences from given axioms), something that mathematicians had always strived for, isn't really that important; more important is a system's descriptive power.
Man is a slave because freedom is difficult, whereas slavery is easy.
he's described this number in a book with a finite number of numbered pages ..... methinks something's fishy here ....
Comment removed based on user account deletion
Of course I haven't RTFB, so maybe this is answered, but I don't believe that randomness is a property of a number, its a property of the method used to generate the number. The reviewer's example of flipping a coin to generate a random binary number is an example of this. I could flip a coin and generate the number 000000 - the method of generation is random, the number itself is clearly reducible and therefore not "random" in the sense described in the review.
I would reserve the term "random" to talk about the generation method, and use more precise terms like "irreducible" for the numbers themselves.
To go further, it may even be that what we mean by a "random" generation scheme is: "a scheme whose generation method I can't predict". This makes randomness a property of a system's knowledge of the generation system. For example, in many situations a computer's psuedo-random number generator is a sufficiently random generation scheme, in some cases (for example cryptography) it is not. psuedo-RNGs are not random (they are deterministic, thus the use of the term "pseudo") but for some uses they effectively are, because the system using the numbers output from them can't (or doesn't need to) predict the next number generated.
So I would propose that "random" refers to the process of generating a number that is in practice non-deterministic in the specific context in which the number is used.
Sailing over the event horizon
I made a PDF version of the book if anyone's interested.
reveals the following:
denumerable
adj.
Capable of being put into one-to-one correspondence with the positive integers; countable.
[From denumerate, to count, from Late Latin dnumerre, dnumert-, alteration of Latin dnumerre : d-, dis-, dis- + numerre, to number; see numerate.]
In keeping with the higher math theme, the definition of 'indenumerable' is left as an exercise for the reader.
I want to drag this out as long as possible. Bring me my protractor.
By way of example, propositional logic is complete.
I'll try to explain it in laymans terms for you...
He means that he did not find a number which is part of an infinite quantity of infinite supply and for which there is also an infinite number of. Get it? Good.
Now, for my part I do not give much credibility to a guy who can't even find a number for which there is an infinite quantity. F*ck, just pick one and there you are! But again, I must concede that to find a number (for which similar number exists in an infinite supply) must be harder to do if you look for ONE specific number and you need to look for it thru an indenumerably infinite supply of those. I imagine the complexity of it must be an indenumerably infinite order of magnitude harder to do then to find the bug I am actually tracking which also exist in an indenumerably infinite supply of in the application I am currently working on.
Now I think I've done my fair share of productivity in this world today and I'll just go back to sleep, thank you.
I'd rather be sailing...
This book is... interesting. Really. Stuffing Franz Kafka, Leibniz and Mahabharata to a math book and ending it with poems, that's a piece of artistic achievement.
Perhaps, should we start some C++ coding in verses?
There you are, staring at me again.
I didn't think it was that hard to define 'random'. Isn't 'random' just a measure of how likely a number is to occur in a set of data. In fact, I have trouble with the concept of a single random number for that reason.
I also thought that, if you generated numbers using some kind of algorithm, then almost by definition they couldn't be truly random.
Anyway, my question is: Is this number 'Omega' some kind of goodness measure for random number generators?
Here's a simple demonstration of denumerable numbers at Paul Bourke's page.
I'm waiting for someone to discover the equation used to generate the sequence of slashdot moderation scores.
Vintage computer adverts: http://www.vintageadbrowser.com/computers-and-software-ads
I am sure there's a "mathematical expression" to express the above description too (though it still remains hard to calculate it :)
/n/ bits of Omega is the program that has /n/ bits of Omega explicitly encoded in it.
It remains _impossible_ to compute it, since the question of whether or not an arbitrary program will halt is uncomputable. The shortest program that can compute
Read the book -- it's free, and proves all of this VERY beautifully (much easier than Turing's original proof).
And it also proves that most real numbers are even worse than Omega -- not only can you not compute them, you can't even name them in ANY WAY. Omega can at least be named; it's "the halting probability."
(Yes, I know; the Tao that can be named is not the true Tao.)
-Billy
If you post HTML Formatted, the entitywill generate a "ö" for you.
You may notice that it is an "o" and the characters "uml" inbetween an ampersand and a semicolon.
I'm sure you can figure out how to umlaut the character "u" with that information.
"Total destruction the only solution" - Bob Marley
The Omega Directive overrides the Prime Directive. All trekkies must destroy this book on bookstore shelves everywhere or else it could spell disaster for the Alpha Quadrant.
I thought "omega" was already taken in number theoretical circles--the surreal number consisting of up-up-up-up-... ("up-hat")? Hell, Cantor broke out the Hebrew numbers to express his weird idea. That link uses omega in its own way. This guy really should have tried a little harder.
blarg.
Have you ever read a math book that was able to carry you through its proofs, heart racing, and make your skin tingle upon reaching its philosophically astounding conclusion?
Slashdot: News for Nerds. Stuff that matters.
The concept that uncountable sets exist is just silly. The sets are simply not well defined. If you can't define something well enough for it to be calculated, then it is not mathematics. Just as I can describe "love" or "happiness", but I cannot give a formal definition of them... they are not math.
These supposed mathematical objects are claimed to exist because someone came up with a formal axiomatic system which assumes they exist. It is a self-fulfilling prophecy.
The problem is that such assumptions result in foundational or metamathematical problems. Formally you can prove the existence of uncountable sets, but semantically all sets are countable. So within the formal system you have one thing, while outside of the formal system you have another... its a sort of semantic inconsistency.
For example, in ZFC set theory you can easily prove that the set of all functions on natural numbers is uncountably infinite. However, the fact that ZFC is a formal system tells us that we can count every function on natural numbers that can be proven to exist in ZFC. This second part cannot be proven within the system, but it is immediate from the fact that finite strings have a one-to-one correspondence with the naturals. So if we assume that ZFC set theory is a formal language for describing the mathematical concept of sets, then we see that an inconsistency exists between the formalism and the mathematical concepts.
Many people, including mathematicians, only think it is necessary to avoid simple inconsistencies... while allowing semantic inconsistencies.
Others, including some of the pioneers of axiomatic set theory, realized that a more constructive foundation was required for mathematics. There are many variations of constructive mathematics. One such branch roughly states that something is mathematical if and only if it can be computed. So mathematical objects are algorithms. This is an interesting formulation of mathematics because all of math is complete, computable, and consistent.
Formal axiomatic mathematics is flawed. In it only guarantees that you have a system for deriving strings in a formal language. It cannot guarantee that these strings have any mathematical meaning. Hence you can derive meaningless things such as a number that cannot be written down or computed to a sufficient decimal expansion.
Omega is not math, its just words. Math invovles precise, absolute concepts. Omega is nothing ore than a formal gesticulation.
A program can certainly create a number shorter than itself. Therefore it does not follow that software can only produce reducable numbers. Or is there an unstated contraint that "random" means infinitely long?
Have you ever read a math book that was able to carry you through its proofs, heart racing, and make your skin tingle upon reaching its philosophically astounding conclusion?
Yes, so I really should buy a book on how to talk to chicks instead.
The sorts of people who reject the Axiom of Choice (disclaimer: I'm still undecided on the matter) insist on a "constructive" set theory--meaning you can't pull examples of sets that "ought to exist" out of thin air, you have to build them out of the Zermelo-Fraenkel Axioms (minus the Axiom of Choice, of course).
They have a distinction between truth and provability. A statement is true if no counterexample exists (can be constructed), and a statement is provable if there exists a proof of it using the ZF axioms. Using the words "truth" and "provability" in that way, it's clear that the unprovability of the continuum hypothesis is itself proof of its truth. If a counterexample could be constructed (a set with cardinality greater than that of the integers and less than that of the reals), the hypotheis would be provably false. But since it's known to be unprovable, it must be impossible to construct such a set. And the nonexistence of a counterexample is the definition of truth.
It may not actually be inconsistent to use a version of set theory that includes the negation of the continuum hypothesis as an axiom (I'll call it the NCH axiom for Negation-Continuum-Hypothesis), but very few mathematicians (even those who accept the axiom of choice) would accept such a system. Informally, axioms are supposed to be self-evident truths. Even the Axiom of Choice merely extends a statement that is provably true in the finite case to the infinite case, but the NCH axiom asserts, for no self-evident reason, the existence of an exotic set with properties that aren't even trivial to define. The Continuum Hypothesis is technically unprovable, but unless you're actually doing formal mathematics you can safely think of it as true.
The original Howling Frog is a fictional character and has no UID.
There should be an "or it will have paradoxical proofs" at the end.
Godel's Incompleteness Theorem does NOT state that no FAS can be complete (any statement that is true under it's notation is provable is true). The first-order propositional calculus & first-order predicate calculus are both complete axiomatic systems (assuming proof of the former, I have done a proof of the latter). It states that any FAS capable of expressing the natural numbers cannot be complete which means no mathematical axiomatic system can yield a complete system. Any system that allow for unrestricted comprehension allows for variants of Russel's paradox - let us have A be the set of all sets that do not contain themselves and only those sets that do not contain themselves. does A contain itself? either answer is contradictory.
I've seen Chaitin present a paper on register allocation. He skilfully held the attention of the entire audience. It wouldn't be surprising if this were a real page turner.
If I ever, ever, get tingly over a math book, someone - I don't care who - shoot me.
42
It has to be 42!!!
main(i){putchar(177663314>>6*(i-1)&63|!!(i<5)<<6)&&main(++i);}
The idea that a statement might be "true" independent of a model appeals to some Platonic view of mathematics. When you're talking about the "truth" and "falsehood" of a statement, you need to specify within which model.
Case in point: there are legitimate reasons to reject the full Axiom of Choice if you're working in the area of Descriptive Set Theory, where statements about determinacy matter. The Axiom of Choice rejects useful (and hyper-strong) statements like "every game on a set is determined" (never mind what 'game' and 'determined' mean). In general weaker versions are used in areas like this, such as the Axiom of Dependent Choice.
The way that the Continuum Hypothesis (CH) was shown to be independent (what you call unprovable) from ZFC was showing that there exist models of both ZFC + CH and ZFC + ~CH. It wasn't shown first that CH is unprovable, with the other statements as corollaries.
In general questions about infinities are not going to affect you as a mathematician but you can't just say 'oh the Continuum Hypothesis is true' if you're working near that area. If you are working in an area where the continuum hypothesis matters (logic), you can't be so flippant. If you're working in an area where it doesn't matter, why bother worrying about such technicalities in the first place?
why, I just don't understand it. Kids these days, what utter slackers. Must be that boogie woogie music you listen to, it eats your branes. Why, back in the day when REAL men learned algebra, we didn't even HAVE grades, we apprenticed, and if you couldn't orally express the factor of the proportionality of the mean square of localised lava flow as a combination of graff-hinderspee spatial nomenclature with the constant moore-livingston entropy tables by the age of three, you were forced to work an extra milking shift in the badger herds!
And we LIKED IT.
Chaitin's ideas are quite profound both in expanding upon theories of computation:
Goedel -> Turing -> Chaitin
and also in opening up new areas of mathematics and physics, much as chaos theory did.
Understand - the randomness Chaitin is dealing with is NOT the pseudo-random output of a transcendental equation, or of finite state automata (ala Wolfram) - these are truly random numbers that are not being computed, but rather revealed.
Chaitin is also a lisp hacker who (at least in previous books) includes lots and lots of code so you can play with the numbers yourself.
His writing style is a little bit too casual for me (lots of exclamation points), but if you want to learn more about TRUE randomness then go to the source.
Also let me add that Chaitin is a really nice guy - sent him some questions after reading one of his essays several years ago and he answered them straight away.
Hello,
;-)
Sure. Naked and wild is funnier
Muaaaaaaaaaaks
--
You'd stumble in my footsteps (Depeche Mode, "Walking in my shoes")
you have got to be KIDDING me......... thats the last time I ever make a joke....
"Slashdot, where telling the truth is overrated but lying is insightful."
Maybe someone can send a copy to the FED or the Bureau of Labor statistics. They do math by divination.
The reviewer is talking about real numbers. Your intuition about randomness is derived from numbers such as one encounters in a computer or a physical instrument. However, these are not real numbers, they are truncations of real numbers. There are only countably many numbers you can represent on a computer, whereas there are uncountably many real numbers.
There's no such thing as a random number on a computer, because once you single a number out for attention, it isn't random anymore. But, in a technical sense revealed by RTFB, "almost all" real numbers can't be counted. They can't be named exactly, in a way that would allow you to generate them to arbitrary precision. This must be so, because such precise name is a computer program, and there are only countably many computer programs. These numbers are "random" in the sense that it is impossible to single one out for special attention. Although "almost all" real numbers are random, you can't specify a single example!
"The good reader is a rarer swan than the good writer."
Chaitin's a pretty random guy, then, is he?
Perhaps we can get him drunk and let him wander around, encoding the direction of every step as a two-bit integer. That should be an adequate source of randomness, provided he's drunk enough.
It was probability, he had just regrouped an equation. Then he said
"and now I will take a p outside".
And proceeded to factor out the "p".
Me and another likeminded smartass started laughing. No-one else seemed to think it was as funny as we did.
emt 377 emt 4
"The probability that an arbitrary program halts is the random real number that Chaitin had been searching for."
That software is called windows. It comes in several versions but all of them garatee an arbitrary program halt!
"What is the smallest integer not definable in 25 words?"
o x. html
Doesn't that define it? No.
You can prove that all descriptions of this form are imprecise.
http://www.dpmms.cam.ac.uk/~wtg10/richardsparad
Slight nitpick here. CH is independent from ZFC because it can be proven that given a model of ZFC there exist both models of ZFC+CH and ZFC + ~CH. We don't know that there is a model of ZFC at all, and cannot, from within ZFC, prove that.
I am not a math guy, at all, I suck at math.
;)
But after reading all this, I could come to only one conclusion -
the only REAL value that "omega" could have, is zero.
zero cannot technically be calculated (as such), and some wonders if its a real number at all.
The idea that omega cannot be calculated in the truest sense means that it cannot actually exist. Why? well, all whole numbers can be calculated, even if you say well zero is just 1 minus 1. thats a calculation. ok, mathspeak omega = n - 1. where n must always be 1. oops, calculated.
this is why this is so messy. and, if we "bend" that rule, meaning thats not a calculation in the truest sense, then there remains only one true answer... zero
so, heres my mathematical proof: omega MUST be zero because zero is the only possible answer that fits all available facts. although there may certainly be other answers
If we desire numbers with a high degree of randomness why don't we just take a precise stop-clock, a radioactive source and a scintillation detector. Measure the time between scintillations, and through away all but the last few digits. That way even if someone knows the half life of your source they still won't be able to guess at the number generated.
Chaitin in a nutshell:
2 .h tml
Take Godel's Theorem, replace the liar paradox (This statement is false!) with Berry's paradox (The first positive integer that cannot be specified in less than a billion words). Explore this idea for the rest of your life.
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unm
Compare with the work of Kolmogorov.
The problem is that your sentence "The probably that an arbitrary program halts is the random real number that Chaitin had been searching for" is not a valid expression in the arithmetical set of axioms that we're working in, and can't be translated into one. Godel worked around this by making his own system that assigned numbers to letter of the alphabet or some such mess I forget - but I don't think you can use this in this case without constructing such a system specifically for your problem...
11*43+456^2
I just started reading this, and it's prefaced by the kafka parable "before the law". I do not deal well with metaphor or allegory, but it seems clear to me that this parable must be saying something more than the trival reading "buerocracy sucks". Especially considering that it's in a math book. What am I missing?
Give me Classic Slashdot or give me death!
There will allways be an algorithim or a set of procedurals (wording ??) that will be able to describe any sequence (uncountable or not) of a limited set of glyphs. In the case of standard decimal fraction math that would be a set of ten digits.
The question is only how to find the apropriate one.
In other words: Encrypt the Bible with the best algorithim you can find and it's just a matter of (very long) time until someone finds an algorithim that decrypts it to a perfect edition of LotR.
Random or not random is simply nothing but a question of the point of view taken in a certain case.
Which makes me expect books like these to be a waste of time.
We suffer more in our imagination than in reality. - Seneca
I did a postdoc with a guy who wrote a book called "An Introduction to Kolmogorov Complexity and Its Applications". Anyway, Chaitin finds out that this book is going to be published and calls my boss, whining that he's not going to call it "An Introduction to Chaitin-Kolmogorov Complexity and Its Applications" -- Chaitin just doesn't get the idea that you have to come up with something *first* to get it named after you.
It is not the case that the "continuum hypothesis is known to be true". Nor is it the case that it has been proven to be unprovable, though that is closer to being correct.
The continuum hypothesis is a statement about entities which do not exist in the universe. We know what the statement "2+2 = 4" is about; it's about integers, and since we can count, we're pretty sure that integers exist. The statement "the universe is expanding" is a statement about things we can observe. There can be quibbles about how much of the universe we can see, whether our understanding is really great enough to answer such questions, and so on, but in the end, practically everyone would say that the question has meaning and, therefore, has some kind of answer, even if the answer is no better than "the parts we can observe indeed appear to be expanding".
The continuum hypothesis is different. It is a statement about uncountable sets, which are creations of our mind. If we are right about the laws of physics, there are *no* uncountable sets existing as physical entities in our universe. What this means is that the continuum hypothesis is not a statement relevant to physical reality, and therefore is of quite different character than either "2+2 = 4" or "the universe is expanding". It is a completely reasonable belief system to hold that the continuum hypothesis, being entirely about non-existent mentally generated entities, has no meaning, and is therefore neither true nor false.
To believe that the continuum hypothesis has a definite truth value is a strong philosophical statement. The mathematical philosophy called Platonism holds that mathematical objects, such as uncountably infinite sets, actually exist, and therefore that statements about them such as the continuum hypothesis have meaning, and in fact that such statements are either true or false. Another philosophy of mathematics is formalism, which holds that mathematics is a game we play according to rules. If someone proves a complicated mathematical result about uncountable sets, we admire this as brilliant play of the game, but do we "believe" it? We believe it only if we believe those statements from which the reault was proved. To play and appreciate the game, we don't have to believe in the axioms, and in fact may find it entertaining to play the game starting from axioms we believe to be false. A formalist is unlikely to regard the continuum hypothesis as either true or false.
Another poster said that the continuum hypothesis has been proven to be unprovable. This is an oversimplification. What has been proven is that the continuum hypothesis is unprovable from the standard set theoretic axioms, using standard logic. A formalist admires this statement as itself brilliant game play, but understands that it is meaningful only for this game. Add another axiom, and suddenly you can prove CH. Unless you find the axioms compellingly true, you probably regard a claim of the truth (or falsity) of CH as dubious as a claim that one's goal in life should be to own Park Place. Truth is relative to where you started from.
A good Platonist on the other hand, will generally believe that the contiuum hypothesis is meaningful, and either true or false, if only we were clever enough to figure out which. Since we know we can't prove it from the standard axioms using the standard logic, a Platonist must hope for discovery of a new axiom or a new logic which is intuitively compelling, and which will also allow CH to be proved or disproved. So, to ask "Is CH true?" is assuming a Platonic view of the Universe, and can be answered only by mathematical creativity ("I propose Axiom X, which settles it"), not merely by a clever play of the game of mathematical deduction.
It is my understanding that most mathematicians who care about these issues are in fact Platonists.
I think you are wrong about prevailing mathematical opinion. Most
mathematicians these days (at least set theorists) would rather adopt
Not CH than CH. For an example of why Not CH is more intuitive, find a
paradox (due to Freiling, I think) about "throwing darts at the real
line." Granted it would be nice to be able to construct a set with
cardinality Aleph_1, but just be adopting AC we are already supposing
the existence of sets we cannot construct.
P.S. According to a prof. I know, there is a movement afoot to take
2^(aleph_0) = aleph_2. Why? I have no clue.
Good point. The consistency of ZFC is something we can never prove and have to assume.
It is common to write umlauts as ae, oe, ue and ss. For the german-speaking crowd on slashdot, this is is easy to read *and* it is very easy to type.
:)
But... IMHO it doesn't really matter, we all know who is Goedel, Godel, Gödel
No, it was not a joke. It was an attempt at a joke. Real jokes are funny. You, however, are less so. The original was almost as bad as your follow up, but you have established a new low.
Simon Singh wrote a couple of books. One is Fermat's Enigma, which is a very entertaining story about how Fermat's Last Theorem was proven. It actually sounds quite boring, but after the first couple of pages, you can't put it down. Even my girlfriend at the time liked it, and she hates math/science/technology.
He also wrote The Code Book, which is basically a walkthrough of encryption over the last few hundred years, how methods were designed, and how they were broken. A good portion of the book is spent on the Enigma cipher from WWII and all of the shenanigans that went on for us to crack it.
Need Free Juniper/NetScreen Support? JuniperForum
It is also noteworthy that his contributions aren't solely in the field of mathematics - he has contributed some groundbreaking work in the area of compiler research, such as this paper.
"I love my job, but I hate talking to people like you" (Freddie Mercury)
Last time math tried to be interesting a Pirate was stealing pizza from a 4th grade class room.
I've got a degree and I got lost less than half way through ... I am hella stoned tho.
When you've come up with an axiomatized and provably consistent logic to which all of English can be reduced, I and a couple of guys named Godel and Wittgenstein would like to know.
Here's a clue. The last time you ever made a joke was much longer ago. Everyone who is not you wishes that you had stopped trying to make jokes.
I heard a great story regarding inifinity and kids. Can't vouch for its veracity but here goes...
A mathematician is talking to a boy of about five years old and asks him, "What is the biggest number in the world?".
The boy replies, "540!".
The mathematician then asks, "What do you get if you add one to that?".
The boy furrows his brow for a moment and then his eyes open wide in astonishment.
Smiling, the mathematician thinks the boy has realised that no matter what number you think is the biggest, you can always add one to it.
"Wow!", the boy exclaims, "I was pretty close then!"
"Where is the wisdom we have lost in knowledge, and where is the knowledge we have lost in information?"-T.S.Eliot
...is that he's really one-upped the other guy since it's (Omega + 1)!, as in (Omega + 1) factorial.
If CH is true, the entire plane can be divided into three disjoint sets S1, S2 and S3, such that S1 is horizontally finite, S2 is vertically finite and S3 is diagonally finite. If you look at glass of water with a straw, it goes half length down, jump, then goes all the way. 4 centimeter look like 3. Same thing that you say.
I suggest you read Slashdot
you here something.... on no thats right I stopped listening to people who could post their name 2 years ago sorry....
"Slashdot, where telling the truth is overrated but lying is insightful."
Are you asking whether I heard something? No, I read something. If you can read silently, you probably did not hear anything, either.
/. are nerdy really does not constitute a joke. If you think your ability to observe and declare the obvious is funny, you are mistaken.
/. has some obvious benefits. It allows one person to point out that someone is being a dipshit without turning it into a personal fight. You seem dumb, humorless and upset. I really don't care for you to know me.
You are not funny. I saw your comment modded up to 5. It was a horrible attempt at a joke. It wasn't funny. It wasn't clever. Stating the obvious and pretending that you made a joke by stating it is simple and stupid. It is pitiful. I was not offended by your comment; I thought it did not deserve the moderation it received. Can you understand? I thought it was a stupid lame unsuccessful attempt at humor. It wasn't a matter of being offensive; it was a matter of how lame it was. Your comment held no insight. There was nothing subtle about it. Good humor adds a twist to the existing facts. Stating that both math and
As for putting my name on anything, "Fools' names, like fools' faces, are often seen in public places." The freedom of anonymous communication on
One more thing, you are a liar. Declaring that you ignore Anonymous Cowards contradicts changing your profile and posting replies. Being two faced is one thing and a bad one. Not having the basic sense God gave most primates to show only one face at a time is just dumb. Showing both faces in a single sentence is way past retarded stupid.
Dishonesty, stupidity and unfunniness do not mix well.
A word of warning: Chaitin is an entertaining writer, but he is not a careful writer. His purely mathematical theorems and proofs are perfectly fine, of course, but when his thoughts turn philosophical, he is prone to fairly idiosyncratic and dubious thinking.
For example, in one article he inexplicably quotes Einstein to make a point about philosophy of math. In the quote, Einstein alleges that mathematical axioms are invented by humans. Chaitin proudly proclaims that this shows Einstein is an "empiricist". This is a very unusual use of the term "empiricist", not at all consistent with what philosophers of mathematics would mean if they used the term.
Chaitin also defines technical terms (like random) and then pretends he uses them in their usual, non-technical sense. But his definition of random is not the same as its usual sense. For Chaitin, there is a non-zero probability that a random source of 0's and 1's produce a "random" string. This probability goes to 0 as the length of the string goes to infinity, but even then the random source may produce a non-random string (it is a possible event with probability 0).
Finally, Chaitin produces his "random" number Omega, and proudly proclaims that he has proven some mathematical claims are "true for no reason". I don't really know what this would even mean, but unless it means "some equations involve random numbers" then it's not clear how he's proved it.
Anyway, my comments are not referring to this new book, which I have not read, but only to a few articles of Chaitin's that I've read in preparation for a course. For a coherent and clear criticism of Chaitin's work, see Panu Raatikainen's articles.
Phiwum's law: anyone that names an obvious law after himself and then puts it in his own sig is just pathetic.
Sorry! Even "preview" doesn't help me spot all my errors.
Chaitin also defines technical terms (like random) and then pretends he uses them in their usual, non-technical sense. But his definition of random is not the same as its usual sense. For Chaitin, there is a non-zero probability that a random source of 0's and 1's produce a "non-random" string. This probability goes to 0 as the length of the string goes to infinity, but even then the random source may produce a non-random string (it is a possible event with probability 0).
Originally, I wrote "random". Sorry again.
Phiwum's law: anyone that names an obvious law after himself and then puts it in his own sig is just pathetic.
All I need is the math text and I'm rock hard. Damn I can barely get through the door.
I knew a guy who, in grad school, shared an office with a female grad student. Late one night went back to the office to get something, and almost tripped over her while she was, um, pleasuring herself. But that's not the good part. The good part is, as he was backing out of the room, he noticed that in her other hand was a math book, (Cohn's Lie Groups, to be precise). He confessed that, although a math grad student himself, he never found the book quite as exciting as she did.
Stories like this renew my faith in my fellow geek. Thank you timothy!
I never really cared about the Axiom of Choice until I realized upon reflection that I am one of the few that reject it. This is because I do have a hard time ascribing "truth" to what you describe as sets that "ought to exist". I think of them as vacuous hypotheticals unless they have demonstrable existence (read are constructable). While I choose not to accept the Axiom of Choice, I am willing to entertain its use in mathematics, and would even encourage it if I knew of tangible results. For similar reasons, I reject real numbers, but encourage their use, as a number of significant results are facilitated by their use. On theoretical grounds, I'd argue for algebraic numbers and talk about reals only as limits of algebraics.
So.... You believe in God right? Or a least a god as the creator of the universe, first cause, prime mover etc?
Damnit I AM acting my age. I'm 15 in hex!
not that this kind of thing would get slashdotted, but Chaitin has a mirror of his website on a University of Maine department of computer science server: Here
Chaitin was given an honorary degree at the University of Maine in 1995, and often gives talks at the school. I'm assuming because the CS department chair at UMaine is an IBM TJ Watson Research Center alumni
Well, that IS the other possibility allowed by Godel's theorem-- systems may be consistent and incomplete, OR complete and self-contradictory, but not both. If you feel that consistency is the hobgoblin of little minds, you can relax and prove most anything you want after assuming (P && !P) as an axiom. =)
//Information does not want to be free; it wants to breed.
Even if the writer's conclusion is true, it is not so obvious as to justify stating it without argument.
All computer programs may be mapped to integers. ("It has been shown")
The integers are a denumerable set. (basic set theory 101)
The set of all computer programs that generate numbers, is itself a subset of the set of all computer programs. (Duh?)
The subset of any denumerable set is denumerable. (basic set theory 101)
All numbers, generated by computer programs that generate numbers, are memebers of a denumerable set. Trivially, QED.
Now, if you want proof of the premise-- that the set of all computer programs may be mapped to integers-- that's another story. (Hint: use a Turing machine and RTFB.) But the conclusion seems blindingly obvious.
//Information does not want to be free; it wants to breed.