Robert J. Marks sometimes uses the paradox of the smallest “uninteresting” number to illustrate proof by contradiction — that is, by creating paradoxes:
By way of illustrating the concept of proof by contradiction, Dr. Marks then offered his proof by contradiction that “all positive integers — numbers like 6 or 129, or 10 100 — are interesting.” If [some positive integers] are not interesting, there is a smallest, non-interesting number. But hey, that’s interesting! That’s the proof by contradiction.
Gregory Chaitin: An uninteresting number would be one whose numerical value is irreducible. And that’s exactly the proof… That’s a very good explanation, because then the next step from that to my incompleteness theorem is to say, “Well, what does ‘interesting’ mean?”
And one good definition of “interesting” is: An interesting number is one that stands out because there is a more concise definition of it or, more precisely, a program that is substantially smaller than its numerical value that calculates it… that’s some way it stands out from the run-of-the-mill numbers. And the run-of-the-mill numbers are ones whose numerical value is an incompressible or irreducible string of bits. So you can sort of go step by step from that paradox about the smallest uninteresting number, which is, ipso facto, interesting, to a proof very similar to mine.
News, “The paradox of the smallest uninteresting number” at Mind Matters News
Don’t miss the stories and links from the previous podcasts:
From Podcast 4:
Why the unknowable number exists but is uncomputable. Sensing that a computer program is “elegant” requires discernment. Proving mathematically that it is elegant is, Chaitin shows, impossible. Gregory Chaitin walks readers through his proof of unknowability, which is based on the Law of Non-Contradiction.
Getting to know the unknowable number (more or less). Only an infinite mind could calculate each bit. Gregory Chaitin’s unknowable number, the “halting probability omega,” shows why, in general, we can’t prove that programs are “elegant.”