Thanks to all 13 of you who completed my online personality quiz, a.k.a. the poll, "What's your favourite transcendental number?" Here I present some feedback, based on the answer you chose:
e. You are a middle-aged, middle-class, moderately intelligent nobody, probably working in the finance department of a middle-size corporation. You vaguely remember something about e from your commerce degree in the 80's, or was it high school mathematics? Regardless, you knew it was smarter to choose this than pi, but didn't want to choose something too outlandish in case you got caught faking it and ended up being thrown out of the liberal party.
pi. You have a vivid memory of grade 6, mainly because you're still in it. Wow! A number that's so long you can't ever write it down! You're unsure why 22/7 is so much more complex than 23/7, but maybe you'll find out in grade 7.
ln(2). You are a geek. You always think in powers of two because you spend your life talking to computers, so ln(2) appealed to you because that's how you know how many megabytes you need for your Java blog mainframe uplink.
Chaitin's constant. You are a try-hard. You went to look this up on wikipedia and what you read was baffling but you thought it would impress other people because it sounded so complicated. Think again.
4. You are a moron. You had to look up transcendental numbers on wikipedia, and you accidentally went to the page on transcendental meditation. That didn't seem to have anything to do with numbers so you just chose 4 because you know it's a number and the other ones are letters or words.
Subscribe to:
Post Comments (Atom)
Posts
10 comments:
Tangentially related to Chaitins omega, a friend of mine recently posed a question to me that I can summarize as: Suppose there are two numbers, of relatively equal size, one that is more memorable (that a person can more easily memorize) but is provably uncompressible. Another number is less memorable but compressible. What are the implications, and is this situation a paradox?
Of course, I think the problem lies in the word memorable, we've taken something very formal and then thrown in something very informal. Once we dirty up the clean prestine rational world of the abstract with the real world, it isn't surprising to come to ridiculous ends. Some how our discussion ended up with a sketch of an argument about turing machines, inherit information in the machine's description itself, and whether the concepts of mind/self are illusory. Which sounds retarded on repeating it, but it actually connects up to the word memorable and how you can maintain a deterministic/physicalist perspective and not have a problem if two such numbers were found.
HA! fer reals yo.
Lastly, if I had voted I would have chosen e, and Walter Rudin would agree with me:
http://www.amazon.com/gp/product/0070542341/ref=pd_lpo_k2_dp_sr_1?pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0024041513&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=023ZW6F7APZ63J2HAX2T
Use the "look inside" this book feature to see the first pages, where in the first page of the prologue he says:
"This is the most important function in all of mathematics" though you can't see it on the page he's referring to e^x
unfortunately the book scanner, somehow missed the e^x that sits all alone centered in the middle of the white space between the Prologue title and the text.
Wow - that's some heavy stuff. I seem to be attracting a more intellectual class of comment in the past few days. Go me!
re your numbers paradox: I feel intuitively uneasy at the thought of a finite number which is provably uncompressable. Is this really possible? I guess it depends what you mean by "compressible" - I'm thinking of factoring, or if the number is prime, factoring N+1. That's a pretty simple scheme that should work reasonably well unless you're one of these people who is good at mathematics and like to shoot down handwavey arguments like that.
In any case, "memorable"-ness in my opinion has much more to do with idiosyncrasies of human cognition than it has to with mathematics.
I actually chose Chaitins Constant because I thought it looked cool. But yes I did have to look it up on wikipedia. I still have no idea what it means and to be honest I don't really want to know.
My word verification for today is "nesse". I looked up the story for this on wikipedia too.
http://en.wikipedia.org/wiki/Randolph_M._Nesse
God bless wikipedia!!
"Randolph" is a name you don't hear much in the schoolyard these days. Suggestion to expecting parents: name your boy Randolph. It's like a cross between "randy" and "Adolf"!
The general problem of constructing a machine or an algorithm that decides if a number is compressible or not, is provably unsolvable by reduction to the halting problem. To sort of answer your question(s): "feel intuitively uneasy at the thought of a finite number which is provably uncompressable. Is this really possible?"
By compressible I am referring to comparing a numbers Kolmagorov complexity.. K(n) to its original size log_2(n). If they are roughly the same order, than the number is essentially uncompressible. If K(n) is much less than log_2(n) then the number is compressible.
This may make your mind explode, but yes there must be instances of provably uncompressable numbers, however identifying the proof maybe undecidable.
This is analogous to how the halting problem is provably undecidable in the general, but that if you intersect the halting problem with the regular language of turing machines less than or equal to some maximum size (that is machines whose description is of a length <= some finite number) what you end up with is a finite language and hence a regular language. As a regular language, it accepted by some determinate finite state machine, and hence decidable.
However, just because you can prove a language is decidable, doesn't mean you can find the machine which decides the language! That is, if I were to give you a machine which decides the language, you may never be able to demonstrate/verify that it in fact decides the language.
woooooo-EEEEEE!!!
I studied a little crazy-maths in my youth. What you say reminds me sufficiently of that to make me uncertain whether you are speaking truth or you just made all that up.
But then I started thinking about it a little more and I realized that by "compressibility", we're talking about being able to store a number using fewer bits than to store its value. For example, it's easier to store the descriptor "1 googol" than to actually store a googol. So of course there must be uncompressible numbers simply by appealing to the pigeonhole principle.
Thanks for stopping by!
Yes there are uncompressible numbers by pigeonhole principle, but thats not what I was arguing. What I was arguing was there are instances of uncompressilbe numbers for which there exists some 'proof' that the number is uncompressible. It's one thing to say there must numbers out there that have some property. It is another thing to say there are numbers which not only have the property but can be proven to have that property.
Furthermore, I was making a claim that I myself have trouble understanding, something about how there are INSTANCES of uncompressible numbers for which there exists a proof of their uncompressibleness. (ok I understand it up to that part) but then I throw in something about their proof being unverifiable. which is when I stop understanding myself. because I have a hard time understanding what a 'proof' is if it fails to demonstrate that said statement is true. But I know that something like this is true (separate from this incompressibility nonsense), here goes:
In first order logics, if I give you a statement S and it's proof P, you can always churn the proof through a machine and verify that the proof does in fact show S to be true. In higher order logics, proof verification is necessarily undecidable, by reduction to universal computation, and the existence of undecidability in universal computation.
Another way to look at this is as follows: That is there are computer programs that do in fact always correctly compute the answer for some well defined problem. However, proving that said computer program in fact computes the answer correctly can itself not be provable.
Which is equivalent to saying: there are sometimes programs out there that do something very well defined, but said programs do so for no good reason. (The statement of their correctness is itself a Godel Statement.)
Hang on, aren't you confusing the concept of "unproveable truth" with the concept of "unverifiable proof"? The example you give in your second last paragraph is what makes me think this. As you say, what is a proof if you can't verify it? Whereas the notion of a statement which is true but unproveable is well known.
Or am I still two steps behind you?
I'm not sure how I feel about the word 'unverifiable proof'. If only for the semantic conundrum of calling something a proof which is unverifiable.
Previously I said:
"In first order logics, if I give you a statement S and it's proof P, you can always churn the proof through a machine and verify that the proof does in fact show S to be true. In higher order logics, proof verification is necessarily undecidable, by reduction to universal computation, and the existence of undecidability in universal computation. "
The above may actually be false. Doing a little googling, it seems proof verification is decidable. Given that you started with a finite number of axioms.
What I was misremembering is the following true statements: You can have both completeness and soundness in first order logics. But the incompleteness theorems show that higher order logics are necessarily either sound or complete but not both.
Either way it seems to me that something weird is going on here. I have been repeatedly told that there is an equivalence between Godel's incompleteness theorems, and Alan Turing's demonstration of undecidablity via the halting problem. They both certainly demonstrate the existance of statements whose truth/falseness can not be determined. But I thought there was a deeper equivalence.
It is this equivalence is what I am struggling to grapple with here. It seems to me proofs and computer programs are equivalent objects, similar to the way that godel uses his numbering system to encoded his logic.
It also seems to me that proof verification is just another theorem but a theorem about the proof itself. That is if I have a statement S and a candidate proof P. I can always ask, "does P prove S?" and we can call that statement T. Is there such a T, that is itself a Godel statement?
My prior googling, seems to say that proof verification is decidable, so there are no such T statements that are Godel statements.
Hrmm...
I disagree that proofs and computer programs are equivalent objects. It seems to me that theorems and programs are equivalent.
Godel's proof involves encoding into a theorem a meta-statement about whether or not it is proveable. The halting problem involves encoding the halting-detection algorithm into a string processable by itself.
So it seems to me that proof of truth or falsehood is similar to a program halting. Some programs don't halt. Some truths are unproveable.
Post a Comment