On Sun, Nov 18, 2012 at 9:22 AM, Henry Baker <hbaker1@pipeline.com> wrote:
FYI -- I wonder how many math proofs down through the centuries have been put into verse?
I think it will be hard to beat this one: (http://math.uchicago.edu/~wald/lit/pi_proof.txt) Kevin Wald: The Pi Proof of Penzance. A proof of the irrationality of pi, to a well-known tune. (First presented to my calculus class a short while ago, in a slightly different version.) Note: the actual mathematical content of this work is based on a proof I saw posted to sci.math a while back. ---------------------------------------------------------------- That pi must be irrational, I claim, is demonstratable: Assume that with a quotient of whole numbers it's equatable -- Say, m o'er n. Define a_k, by fiat dictatorial, For every natural k to be one over k factorial Times integral from naught to pi of (n times (t)(pi - t)) To power k, times sine (or for you Latin scholars, _sinus_) t, dt. These a's are *positive*, with *finite sum* (indeed, it e- Quals integral exp(n times (t)(pi - t)) sin t dt). Chorus: It's integral exp(n times (t)(pi - t)) sin t dt! It's integral exp(n times (t)(pi - t)) sin t dt! It's integral exp(n times (t)(pi - t)) sin t dt, dt! But integrate by parts -- each a's the sum of the preceding two Times integers, a_naught is 2, a_1's 4n, thus leading to (since *all* must then be integers) a contradiction statable, And thus that pi's irrational, you see, is demonstratable! Chorus: Since *all the a's are integers*, a contradiction's statable, And thus that pi's irrational, we see, is demonstratable!
http://m-phi.blogspot.nl/2012/03/geoff-pullum-seusses-out-halting.html
Wednesday, 21 March 2012
Pullum S(e)usses Out the Halting Problem
Since 2012 is the Turing Centenary Year, and since incompleteness/diagonalization has been the dominant theme on M-Phi of late, I thought it would be both fun and appropriate to repost Geoff Pullum's delightful Seussification of Turing's proof of the undecidabilty of the halting problem. (H/t to John Baez over on Google+.)
Scooping the Loop Snooper
No program can say what another will do. Now, I won’t just assert that, I’ll prove it to you: I will prove that although you might work til you drop, You can’t predict whether a program will stop.
Imagine we have a procedure called P That will snoop in the source code of programs to see There aren’t infinite loops that go round and around; And P prints the word “Fine!” if no looping is found.
You feed in your code, and the input it needs, And then P takes them both and it studies and reads And computes whether things will all end as they should (As opposed to going loopy the way that they could).
Well, the truth is that P cannot possibly be, Because if you wrote it and gave it to me, I could use it to set up a logical bind That would shatter your reason and scramble your mind.
Here’s the trick I would use — and it’s simple to do. I’d define a procedure — we’ll name the thing Q – That would take any program and call P (of course!) To tell if it looped, by reading the source;
And if so, Q would simply print “Loop!” and then stop; But if no, Q would go right back to the top, And start off again, looping endlessly back, Til the universe dies and is frozen and black.
And this program called Q wouldn’t stay on the shelf; I would run it, and (fiendishly) feed it itself. What behaviour results when I do this with Q? When it reads its own source, just what will it do?
If P warns of loops, Q will print “Loop!” and quit; Yet P is supposed to speak truly of it. So if Q’s going to quit, then P should say, “Fine!” – Which will make Q go back to its very first line!
No matter what P would have done, Q will scoop it: Q uses P’s output to make P look stupid. If P gets things right then it lies in its tooth; And if it speaks falsely, it’s telling the truth!
I’ve created a paradox, neat as can be – And simply by using your putative P. When you assumed P you stepped into a snare; Your assumptions have led you right into my lair.
So, how to escape from this logical mess? I don’t have to tell you; I’m sure you can guess. By reductio, there cannot possibly be A procedure that acts like the mythical P.
You can never discover mechanical means For predicting the acts of computing machines. It’s something that cannot be done. So we users Must find our own bugs; our computers are losers! _______
Pullum, Geoffrey K. (2000) “Scooping the loop snooper: An elementary proof of the undecidability of the halting problem.” Mathematics Magazine 73.4 (October 2000), 319-320.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com