What do you think?
Rate this book
The LIMITS of MATHEMATICS: A Course on Information Theory and the Limits of Formal Reasoning
As a teenager, Greg created independently of Kolmogorov and Solomonoff, what we call today algorithmic information theory, a sub ject of which he is the main architect. His 1965 paper on gedanken experiments on automata, which he wrote when he was in high school, is still of interest today. He was also heavily involved in IBM, where he has worked for almost thirty years, on the development of RISC technology. Greg's results are widely quoted. My favorite portrait of Greg can be found in John Horgan's-a writer for Scientific American-1996 book The End 01 Science. Greg has gotten many honors. He was a guest of distinguished people like Prigogine, the King and Queen of Belgium, and the Crown Prince of Japan. Just to be brief, allow me to paraphrase Bette Davis in All About Eve. She said, "Fasten your seat belts, it's going to be a bumpy talk!" Ladies and Gentlemen, Greg Chaitin! [Laughter & Applause] CRISTIAN CALUDE introducing GREGORY CHAITIN at the DMTCS'96 meeting at the University of Auckland.
162 pages, Hardcover
First published January 1, 1997
2 people are currently reading
162 people want to read
About the author
Gregory Chaitin
23 books43 followersGregory Chaitin is widely known for his work on metamathematics and for his discovery of the celebrated Omega number, which proved the fundamental unknowability of math. He is the author of many books on mathematics, including Meta Math! The Quest for Omega. Proving Darwin is his first book on biology. Chaitin was for many years at the IBM Watson Research Center in New York. The research described in this book was carried out at the Federal University of Rio de Janeiro in Brazil, where Chaitin is now a professor. An Argentine-American, he is an honorary professor at the University of Buenos Aires and has an honorary doctorate from the National University of Cordoba, the oldest university in Argentina.
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 5 of 5 reviews
November 29, 2014
It seems to me that Chaitin's intelligence and abilities as a mathematician are undeniable. Considering this, why would I give such a low rating to The Limits of Mathematics? As I see things there are two main problems.
The first problem is a common trend in academic publications. This book is transcribed directly from a lecture. (Watch out for typos in the equations!) Chaitin wrote his lecture with an audience of listeners in mind, and neither Chaitin nor the publisher made any real attempt to rewrite The Limits of Mathematics to make it more intelligible to a reader. It took several readings and much thinking to make his ideas seem less ephemeral and more concrete. Many details are missing, and it is entirely up to the reader to reconstruct the thought process that leads to what Chaitin calls the halting probability--denoted by Omega. It is also largely up to the reader to see exactly how Omega implies the results that Chaitin claims. Let me be clear, I am not opposed to working on something myself. Often this is the best way to understand, but here it feels like there is no ground to stand on.
Mathematicians often redefine commonly used words in an exact technical sense. For most people it takes training to not confuse the technical meaning of a word with its common meaning. This is equivocation. On my first reading of Chaitin's results, perhaps from being young and not careful to avoid equivocation myself, or perhaps from being in awe of Chaitin's obvious intelligence, I thought the results contained in The Limits of Mathematics were more profound than they actually turned out to be once I understood.
This brings me to my second problem. Chaitin equivocates in order to sell us on the profoundness of his results. After a few readings, a question posed by an audience member on page 13 finally allowed me to connect all the pieces of the puzzle.
"Question: I can't see why Omega should be a probability. What is two one-bit programs both halt? I mean, what if the two one-bit programs both halt and then some other program halts? Then Omega is greater than one and not a probability." (Chaitin's construction of Omega relies on the length of a each program that halts)
"[Chaitin's] Answer: I told you no extension of a valid program is a valid program."
This is a prefix code. Although Chaitin never uses the phrase 'prefix code' his answer indicates that he is limiting his construction of Omega to prefix codes only. Mathematically this is not a problem, but it is also certainly true that machine languages and commonly used high level programming languages are not prefix codes. It may be countered that for any particular language all programs are countable, and prefix codes are also countable. For each language there is always the possibility of a one-to-one correspondence with a prefix code. However, once this is done the interpretation of Omega as a halting probability becomes problematic. Mathematically it is still a probability, but by our common sense notion of probability it is not the probability that any C++ or Java or Haskell program will halt. It is not even the probability that any given Turing machine with binary input will halt on a randomly formed input string. By common sense notion of probability what I mean is the ratio of halting programs to all programs in the limit as program size becomes larger. It is only a probability in this sense when considering prefix codes directly. If the one bit program of 1 halts, then all programs beginning with 1 must also halt.
I do not intend to make anyone doubt the mathematics. Rather, my intention is warn readers against the trap of equivocation. His mathematical results are solid and interesting in their own right. For instance, his proof that Omega is a normal number actually provides us with a possibly infinite list of normal numbers. Because Omega is constructed from a prefix code, each prefix code possibly yields a different Omega. Another result is that for a given prefix code Omega is uncomputable in the strict mathematical sense of 'computable', but again to those of you looking for philosophical insight be weary of Chaitin's claims. Here the word 'computable' doesn't match most non-mathematicians' common sense understanding of computable. What 'computable' means here is that there is no computation that will enumerate Omega digit by digit producing the correct nth digit each time. But by Chaitin's own programs that come with The Limits of Mathematics we can calculate Omega in the limit from below. In the non-technical sense of the word 'computable' I would dare say that most people would intuitively consider this computable.
The first problem is a common trend in academic publications. This book is transcribed directly from a lecture. (Watch out for typos in the equations!) Chaitin wrote his lecture with an audience of listeners in mind, and neither Chaitin nor the publisher made any real attempt to rewrite The Limits of Mathematics to make it more intelligible to a reader. It took several readings and much thinking to make his ideas seem less ephemeral and more concrete. Many details are missing, and it is entirely up to the reader to reconstruct the thought process that leads to what Chaitin calls the halting probability--denoted by Omega. It is also largely up to the reader to see exactly how Omega implies the results that Chaitin claims. Let me be clear, I am not opposed to working on something myself. Often this is the best way to understand, but here it feels like there is no ground to stand on.
Mathematicians often redefine commonly used words in an exact technical sense. For most people it takes training to not confuse the technical meaning of a word with its common meaning. This is equivocation. On my first reading of Chaitin's results, perhaps from being young and not careful to avoid equivocation myself, or perhaps from being in awe of Chaitin's obvious intelligence, I thought the results contained in The Limits of Mathematics were more profound than they actually turned out to be once I understood.
This brings me to my second problem. Chaitin equivocates in order to sell us on the profoundness of his results. After a few readings, a question posed by an audience member on page 13 finally allowed me to connect all the pieces of the puzzle.
"Question: I can't see why Omega should be a probability. What is two one-bit programs both halt? I mean, what if the two one-bit programs both halt and then some other program halts? Then Omega is greater than one and not a probability." (Chaitin's construction of Omega relies on the length of a each program that halts)
"[Chaitin's] Answer: I told you no extension of a valid program is a valid program."
This is a prefix code. Although Chaitin never uses the phrase 'prefix code' his answer indicates that he is limiting his construction of Omega to prefix codes only. Mathematically this is not a problem, but it is also certainly true that machine languages and commonly used high level programming languages are not prefix codes. It may be countered that for any particular language all programs are countable, and prefix codes are also countable. For each language there is always the possibility of a one-to-one correspondence with a prefix code. However, once this is done the interpretation of Omega as a halting probability becomes problematic. Mathematically it is still a probability, but by our common sense notion of probability it is not the probability that any C++ or Java or Haskell program will halt. It is not even the probability that any given Turing machine with binary input will halt on a randomly formed input string. By common sense notion of probability what I mean is the ratio of halting programs to all programs in the limit as program size becomes larger. It is only a probability in this sense when considering prefix codes directly. If the one bit program of 1 halts, then all programs beginning with 1 must also halt.
I do not intend to make anyone doubt the mathematics. Rather, my intention is warn readers against the trap of equivocation. His mathematical results are solid and interesting in their own right. For instance, his proof that Omega is a normal number actually provides us with a possibly infinite list of normal numbers. Because Omega is constructed from a prefix code, each prefix code possibly yields a different Omega. Another result is that for a given prefix code Omega is uncomputable in the strict mathematical sense of 'computable', but again to those of you looking for philosophical insight be weary of Chaitin's claims. Here the word 'computable' doesn't match most non-mathematicians' common sense understanding of computable. What 'computable' means here is that there is no computation that will enumerate Omega digit by digit producing the correct nth digit each time. But by Chaitin's own programs that come with The Limits of Mathematics we can calculate Omega in the limit from below. In the non-technical sense of the word 'computable' I would dare say that most people would intuitively consider this computable.
February 16, 2024
This is a very dated book on a very esoteric subject... but for me, its nomenclature brought back memories of my start in professional computer software at IBM... a trip down memory lane. But most won't know/care what the heck this book is talking about. It's basic subject remains relevant and is seriously discussed in up to date books by less boastful authors.
September 14, 2021
There's something really important in his work that I can catch glimpses of. The trouble is that this is the fourth or fifth book of his that I've read, and he hasn't told quite the same story twice. I don't care about the exact size of the constants. I want to understand the proof by contradiction.
October 14, 2013
I normally don’t do this, but I’m going to copy/paste this review across three separate books: Chaitin’s “The Unknowable”, “The Limits of Mathematics”, and “Exploring Randomness”.
All three are all thin, overpriced, but very approachable books on Algorithmic Information Theory. Themes include:
- Undecidability, as the basis of formulating a new kind of randomness measure for numbers that have already been generated (not just restricting randomness measures to the processes that generate numbers).
- Chaitin’s Omega constant, which is the probability that universal Turning machine will halt on random input. This constant is “maximally unknowable”, but that doesn’t stop one from performing math with it.
- Philosophy surrounding these topics.
One might underestimate Kolmogorov’s contributions, given how ridiculously self-promoting Chaitin has been with this AIT. However, the topics are interesting enough that he’s easy to forgive. And he uses many code demonstrations (LISP) to make concrete examples out of the math.
All three are all thin, overpriced, but very approachable books on Algorithmic Information Theory. Themes include:
- Undecidability, as the basis of formulating a new kind of randomness measure for numbers that have already been generated (not just restricting randomness measures to the processes that generate numbers).
- Chaitin’s Omega constant, which is the probability that universal Turning machine will halt on random input. This constant is “maximally unknowable”, but that doesn’t stop one from performing math with it.
- Philosophy surrounding these topics.
One might underestimate Kolmogorov’s contributions, given how ridiculously self-promoting Chaitin has been with this AIT. However, the topics are interesting enough that he’s easy to forgive. And he uses many code demonstrations (LISP) to make concrete examples out of the math.
Want to Read
September 25, 2010Review at http://shebang.ws/the-limits-of-mathe....
Displaying 1 - 5 of 5 reviews