A Dictionary For Reading Proofs
What those phrases really mean 
Eduardo Tengan is a mathematician at the Institute for Mathematical Sciences and Computation in Sao Paulo, Brazil. He has written a delightful set of notes titled, “An Invitation to Local Fields.” He also has a great sense of humor. Go check his home page for a proof.
Today I thought I would quote some of his cool comments and add some of our own.
Mary Jean Harrold
Mary Jean has passed away—she is already greatly missed
Mary Jean Harrold started like many of her generation, as a math major. She earned her BS and MA degrees in mathematics from Marshall University. Then she received her MS and PhD degrees in computer science from the University of Pittsburgh.
Today I will talk about Mary Jean. I talk with sadness because she passed away this week, but also with appreciation. Read more…
Littlewood’s Law
Why it may take a ‘miracle’ to catch some cheaters
|
|
source, where he’s right after Charles Dickens |
John Littlewood really existed. He appeared as second author on so many papers with Godfrey Hardy that some believed him to be a fictional appendage. He kept on writing papers for a quarter century after Hardy’s death in 1947 and lived into his 90’s, passing away in 1977. Read more…
Teacher Teach Yourself
How teaching helps you understand proofs
Stanislav Žák is a theorist who has made important contributions to complexity theory. He was at the Institute for Computation Techniques of the Technical University in Prague thirty years ago when he proved the theorem below. He is now affiliated with the Institute of Computer Science of the Czech Academy of Sciences, where he has just written a new paper on “A Turing Machine Distance Hierarchy” with his colleague Jirı Šıma. He should not be confused with Professor Stanislaw Żak of Purdue’s ECE Department.
Today I want to discuss a classic theorem of Žák that is in the textbooks, and why it is a bit tricky to understand.
Read more…
Space Is Easier Than Time
We really understand the complexity theory of space
Anil Ananthaswamy is the author of the book The Edge of Physics. He also consults for Britain’s New Scientist weekly magazine, and wrote an interesting article on space and time entitled, “Space vs time: One has to go—but which?” He started the article with this:
TO ISAAC NEWTON, space was the “sensorium of God,” the organ through which the deity surveyed His creation. It was absolute, unchanging, infinite. Flowing through it “equably without regard to anything external,” as Newton wrote in his great physical treatise, was another similarly absolute heavenly creation: time.
Today I wish to talk about what we know about space, not space as viewed by Newton, but space as used in complexity theory. For us complexity theorists, space is a measure of the cost of a computation of a Turing Machine (TM). It is the number of squares that a TM uses during a computation. It is not an “organ,” nor is it absolute and unchanging; it is simply the number of different cells written to by the computation. Meanwhile time is the number of steps that a TM takes during a computation. Read more…
Euler’s Constants
Having a constant named after you is cool
Jeffrey Lagarias was a Distinguished Member of Technical Staff at AT&T Bell Laboratories for years, and later joined the math department at the University of Michigan, while still keeping involved with the “labs.” His early background is in deep aspects of number theory, and he still works in that area. He has also broaden his interests into other parts of mathematics and theoretical computer science.
Today I wish to talk about a beautiful survey paper he has just published on Euler’s constant in the AMS Bulletin. Read more…
More on the Diagonal
A different angle on the Halting Problem
|
|
src |
Rudolf Carnap was a German-born philosopher who became a mainstay of the famous “Vienna Circle.” Kurt Gödel often visited their meetings, but was not a member. Perhaps, to quote Groucho Marx, Gödel did not want to belong to any club that would have him as a member. However, there was definitely a connection between him and Carnap. As attested by Warren Goldfarb, Carnap “introduced Gödel to logic, in the serious sense.” Further it was Carnap in 1934, not Gödel himself, who drew a strong connection between Georg Cantor’s diagonal argument and Gödel’s incompleteness theorems—see Goldfarb and these three essays by Haim Gaifman.
Today Ken and I want to talk about diagonalization and the Halting Problem. Read more…
D Plus O Equals Do
Our 500th post comes with a non-Federal proposal
|
|
Cropped from HeinOnline source. |
Barack Obama is the 44th President of the United States, and the 43rd person to hold that office. Stephen Cleveland counts as both the 22nd and 24th President since he had two non-consecutive terms, and he remains the only one ever called “Big Steve.” Our Barry, as he is sometimes called, likes to play up the ‘O’ in symbol and speech, and even named his first dog Bo for his initials. As mavens of asymptotic notation we might like to call him “Big-O,” but Obama’s many vociferous critics would read the O a different way. O well.
Today we make post number 500, ‘D’ in Roman numerals, and combine that with ‘O’ to frame some remarks made by the President last week about higher education.
A World Without Randomness
What if there were no coin flips?
|
|
By permission of Hector Zenil, artist. |
Leonid Levin has originated many great ideas in our field. Indeed he had a share with Stephen Cook in the idea of 
Today Ken and I want to use Levin’s ideas to talk about what the world would be like if there were no randomness, no coin flipping, not even with slightly biased flips.
Read more…
Euclid Strikes Back
An application of Euclid’s famous proof there are an infinite number of primes
Euclid of Alexandria, Euclid for short, composed one of the most influential books ever written on mathematics. His Elements served as the textbook for geometry for almost two thousand years. Elements also included basic theorems on what we call number theory today. His proof that there are arbitrarily large primes is a gem.
Today I plan to use Euclid’s gem to solve a “puzzle” that I think you may like.
