## Wednesday, August 03, 2005

### Moons and Planets

When I was in grade school we learned that Jupiter had twelve moons. We had a test. "How many moons does Jupiter have?" I wrote "12" and it was marked correct. In 1974 a thirteenth moon was discovered. The moon didn't just pop into existence in 1974, it was always there (at least when I took my test). Now we know Jupiter has at least 63 moons. The answer of 12 wasn't even close; what I was taught to be a fact was simply not correct.

Now we have ten planets (or is it eight?) circling our sun. Is nothing sacred? What about "My very educated mother just served us nine pies?" What other "facts" from my childhood were incorrect. Are we sure we just have one sun in our solar system?

Maybe that's why I like mathematics and theoretical computer science. Eight plus seven will always be fifteen; nondeterministic space will always be closed under complement. We know what we know; we know what we don't know; sometime what we didn't know we now know but nothing we knew later becomes false.

#### 9 comments:

1. Your post harks back to an earlier post of yours which can be synthesized as: What "facts" taught in the childhood of some current students (say, in Kansas) are wrong?

2. I think that's eight planets. Astronomers seem to think that pluto and this new thing don't count as planets (but they do as Kuiper Belt Objects) and I'm fine with that.

3. No, even in computer science the truth is time-dependent. The prefix "kilo-" used to mean 1000; now it sometimes means 1024. Computer scientists added a 2.4% tax.

4. Suppose for a minute that, 25 years ago, someone had proven that factoring was hard. If you had taken a computational complexity exam, "factoring is hard" would have been a correct answer. Then along comes Peter Shor in 1994. In fact, even in mathematics the truth is time dependent. Take for example sphere eversion. There were several widely-believed "proofs" that sphere eversion was impossible until Smale came along in 1958. My only point is that people, (even mathematicians!), are fallible. Mistakes might not happen as often in computer science and mathematics as in, say, astronomy, but they still happen.

-Steve

5. The old mantra was that factoring is hard. The new mantra is that quantum computation is hard. It's TOTALLY different. :-)

6. Let's hope the tenth "planet" has a name that begins with "t". "My very educated mother just served us nine pies TODAY". Or if another planet is discovered, name them with "l" and "w" for ". . . nine pies LAST WEEK".

In the spirit of moon.google.com, I'm still waiting for europa.google.com, io.google.com, ganymede.google.com . . .

---O

p.s. 12 (base 61) = 63 (base 10). Alternatively, 12 (base 61) = 64.512 (base 10) using Kuperberg's Principle of Expansion. 1.512 new Jupiter moons will be discovered by computer scientists.

7. You are right.But since some proof techniques become harder and harder, it takes longer time to truly know what we know and what we do not know.
For example, the four color theorem was "prooved" by Kempe in 1879. It took quite a time (11 years) to find out that a proof is incorrect (an error in the proof was discovered by Heaver). Kempe submitted his proof to the American Journal of Mathematics. Story read the paper before publication, made simplification in the proof and reported to he Scientific Association of Johns Hopkins University.
Before a mistake in the proof of Kempe was foudn, many people "KNEW" the answer to the Four-Color theorem. Kempe was ellected a Fellow of the Royal Society and was knighted.
Tait "prooved" the same theorem in 1880. Again it took 11 years to find out that Tait's proof is incorrect.

8. But since some proof techniques become harder and harder, it takes longer time to truly know what we know and what we do not know.

I think the advancements of computer-aided theorem-proving will solve this problem mostly. I believe that in the near future, every published math proof will have two parts: An informal part, similiar to proofs we know today, and a formal part, which is a perfectly formal deduction of the theorem. Only the most hardcore postmodern philosophers will doubt these deductions.

We need smarter automatic theorem-provers, and even more importantly, more seamless human-machine interaction to achieve this. But I think it's not that far away.

9. I think I read somewhere that there were "proofs" that Gaussian elimination was optimal before Strassen discovered his algorithm.