This work is licensed under a
Creative Commons License.
|
Friday, March 26, 2004
Teaching High School PhysicsIn a comment on my last post, Suresh Venkat said "On the other hand, we teach school-age children Newtonian physics without laying out a careful argument why the thesis must hold."
This caught me as strange so I asked one of our Indian graduate students how he learned physics in school. He said they were given the appropriate theory and formulas. I asked if they did experiments. He said they were given descriptions of experiments on exams and had to predict the outcome but they never actually performed any experiments.
This is in sharp contrast to my high school physics class in New Jersey. We did many experiments in small groups as well as some class demonstrations to show that the predictions of the theory roughly corresponded to reality. My favorite demonstration simulated the following thought experiment: If a person aims a gun directly at a monkey in a tree and the monkey, scared of the sight of the gun, falls out of the tree at exactly the time the gun was shot, the bullet will hit the monkey since gravity affects the horizontally moving bullet and the vertically moving monkey exactly the same.
My physics teacher attached a stuffed monkey to the ceiling via an electromagnet. He had a device that fired a metal ball at the monkey that was rigged so the magnet would cut out and the monkey would fall at the same time as the ball was fired. True to the theory, the ball hit the monkey in mid-air. Of course there was that hole in the blackboard from the one year the monkey didn't fall.
Which teaching method is superior? In India they can go into more depth in the theory since they don't spend time on experiments. However I don't think you truly get an understanding for a scientific principle without getting your hands dirty.
Update: Venkat responds on his weblog. Perhaps I shouldn't have generalized Indian education from one data point.
2:39 PM # Comments []
Wednesday, March 24, 2004
EvolutionShould public schools in the US teach creationism in addition to or in place of evolution? As a scientist I have to say "no," though I'm preaching to the choir in this weblog.
Often in the news we hear of states and school districts that try to pass laws to teach creationism in schools? We should fight these attempts but we need to do so in a careful manner. Scientists should not impose the truth on school-age children, that will make us no better than the creationists who wish to impose their version of the truth. Instead we need to explain the reasoning behind evolution, the same holds for any scientific principle we teach. For example, I can't expect students to trust me when it comes to the Church-Turing thesis but instead I need to lay out a careful argument why the thesis must hold.
One should not force students to accept evolution, rather lay out the arguments and let the students learn to believe evolution on their own. Only then will they become true believers.
6:06 PM # Comments []
Tuesday, March 23, 2004
Is Satisfiability Checkable?Time for another of my favorite open questions: Is Boolean Formula Satisfiability (SAT) checkable?
The best notion of program checking comes from a paper by Manuel Blum and Sampath Kannan. Let P be a program claiming to compute a language L. A program checker M for L is a probabilistic polynomial-time Turing machine with access to P as an oracle that outputs either "P(x)=L(X)" or "P incorrectly computes x on some input."
We say L is checkable if for all oracle P and inputs x,
If P is correct on x and incorrect somewhere else, MP(x) can output either answer.
- If P(x)≠L(x) then with high probability MP(x) outputs "P incorrectly computes x on some input", and
- If P=L then with high probability MP(x) outputs "P(x)=L(x)".
Blum and Kannan show a nice connection to interactive proofs. We say a language L has a function-restricted interactive proof (FRIP) if there is a PCP for L where the proof for x in L is computable with an oracle for L. We have the following equivalence for all languages L
Checkable languages include Graph Isomorphism, the Permanent and all of the PSPACE-complete and EXP-complete sets.
- L is checkable.
- Both L and L have FRIPs.
Back to whether SAT is checkable. SAT has a FRIP by using self-reduction. So whether SAT is checkable is equivalent to whether SAT has a FRIP.
All of the known PCPs for SAT seem to require counting, a prover hard for #P or at least ModkP for some k. Whether one can find a PCP for SAT that is even in the polynomial-time hierarchy remains open.
Perhaps one can show some consequence of the checkability of SAT perhaps that the polynomial-time hierarchy collapses. Bogdanov and Trevisan have the best result in this direction; they show that if SAT has a non-adaptive self-corrector then PH collapses to third level. Though many checking results use self-correction there still could be some completely different way to show SAT is checkable.
6:25 AM # Comments []
Monday, March 22, 2004
AT&T ResearchThe Newark Star-Ledger has an article about the downfall of AT&T research. Quantum Algorithms has some follow-up quotes by Bjarne Stoustrup.
No doubt that these industrial research labs can produce great ideas and results especially at the scale of AT&T or Bell Labs before the split. But the business model doesn't work; AT&T failed to capitalize on most of the innovations of its labs nor has any corporate labs with an open and unfettered research staff produced valuable intellectual property for that company. If a corporation tries to limit an open and unfettered environment, the best scientists will often leave for other labs or academia.
Bell Labs/AT&T had a lengthy history helped along by a telephone monopoly. But until someone finds the right business model, we will never see a truly self-sustaining industrial basic research lab.
8:53 AM # Comments []