This work is licensed under a
Creative Commons License.
|
Saturday, April 12, 2003
Articles on Quantum and DNA ComputersA couple of interesting pieces in the New York Times.
Jim Holt reviews George Johnson's A Shortcut Through Time: The Path to the Quantum Computer. I haven't seen Johnson's book yet but the more I read about the more I recommend it to laypeople who are interested in quantum computers. It really seems like he gives an understanding of quantum computation without overly hyping the topic.
There is also an article from the circuits section on new work on at the Weizmann Institute on DNA computers. As typical with articles on DNA computing in the New York Times, you should read the end of the article first. That way you get the reality before the hype.
6:28 AM # Comments []
Tuesday, April 08, 2003
Razborov on UnprovabilityIn the old commenting system, Daniel Varga had the following comment on my post on unprovability.
I guess Alexander Razborov turned to the study of Propositional Proof Systems because he wanted to prove that "proving SAT is not in P/poly" is hard in a formal sense. What is his opinion about undecidability? (Of course I know I should ask him, but he doesn't have such a nice message board. :))
I passed the question to Razborov and here is his response.
Dear Daniel, First, I understand that "undecidability" in your question should read "unprovability" (or, otherwise, I misunderstood it). And the answer to it very much depends on the strength of the formal theory we are interested in. For classical theories like Peano Arithmetic or Set Theory I do not have enough intuition (not even to mention evidence) to articulate any opinion. The only thing which seems quite sure to me is that such an independence result, if true, would not be much easier to prove than the original P vs. NP question itself... If we, however, descend in the logical hierarchy to weaker theories capturing poly-time computations (commonly known as Bounded Arithmetic), the answer becomes quite different. I do conjecture that "SAT is not in P/poly" is independent from these theories. Moreover, I believe that if we allow ourselves a standard cryptographic assumption (FACTORING is hard, for definiteness) this question might be more attainable with currently known techniques than those discussed above. Further, I expect that if we ever manage to prove such an independence result, its proof would be very illuminating in approaching the question "what's next and what are we missing?" (cf. Natural Proofs). Finally, let me mention that the introduction to the paper "Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution" (available from my Web site) contains an expanded version of some of these views. Alexander.
4:22 PM # Comments []
CommentsBecause of the popularity of the war weblogs, the Haloscan commenting system I was using was being overloaded which would on occasion cause my web log to have errors and require a long time to load. To avoid this I'm now using cgiComments which I am hosting myself.
The major negative is that I have lost all of the old comments. I apologize for this. Please feel free to repost your old comments or add new ones.
12:21 PM # Comments []
Computation Beyond Turing Machines?In the April issue of the Communications of the ACM, Peter Wegner and Dina Goldin have a technical opinion entitled Computation Beyond Turing Machines. From the article: "Turing machines are inappropriate as a universal foundation for computational problem solving and computer science is a fundamentally non-mathematical discipline". Those are fighting words and luckily I have this weblog to fight back.
Wegner and Goldin's main argument is summed up towards the end of the article. "In the last two decades, computing technology has shifted from mainframes and microstations to networks and wireless devices, with the corresponding shift in applications from number crunching and data processing to embedded systems and graphical user interfaces. We believe it is no longer premature to encompass interaction as part of computation. A paradigm shift is necessary in our notion of computational problem solving, so it can provide a complete model for the services of today's computing systems and software agents."
In here they have a good point. The area of human-computer interaction is sometimes more art than science. But while the basic model of the Turing machine is a sequential device, theoretical computer scientists have come up with variations that capture networks and other aspects of interaction, some of which are described in the Wegner-Goldin article. And all of these new models can be simulated by Turing machines. The Turing machine remains supreme as the model that captures all computation.
Far more troubling is the following: "Gödel had shown in 1931 that logic cannot model mathematics and Turing showed that neither logic nor algorithms can completely model computing and human thought." This is a complete misreading of Gödel and Turing. Not every mathematical statement has a logical proof, but logic does capture everything we can prove in mathematics, which is really what matters. Likewise, Turing machines captures everything we can compute. And what we can compute is what computer science is all about.
10:02 AM # Comments []
Monday, April 07, 2003
Math Riots Prove Fun IncalculableMy post on Fermat's last theorem last week reminded me of my personal all-time favorite math parody, a Chicago Tribune column written by Eric Zorn.
Zorn, grandson of the mathematician Max Zorn, wrote this column that put Wiles' proof of Fermat in a context of the Chicago Bulls basketball team winning a recent championship. I was in the CS department at the University of Chicago during that time and the parallels hit home for me: "Andrew Wiles" = "Michael Jordan", "Yoichi Miyaoka" = "Charles Barkley", "Rie-Peat" = "Three-peat", "Doing set theory in a New Jersey library" = "Gambling in Atlantic City", etc. You get the picture.
Or maybe you had to be there. After this article made the email rounds, one European professor asked me if there really were graduate students rioting in Chicago. Go figure.
3:50 PM # Comments []