The SuperScott and Morgan Freeman FAQ
Update (Sept. 3): When I said that “about 5000 steps” are needed for the evolutionary approach to color an 8×8 chessboard, I was counting as a step any examination of two random adjacent squares—regardless of whether or not you end up having to change one of the colors. If you count only the changes, then the expected number goes down to about 1000 (which, of course, only makes the point about the power of the evolutionary approach “stronger”). Thanks very much to Raymond Cuenen for bringing this clarification to my attention.
Last week I appeared on an episode of Through the Wormhole with Morgan Freeman, a show on the Science Channel. (See also here for a post on Morgan Freeman’s Facebook page.) The episode is called “Did God Create Evolution?” The first person interviewed is the Intelligent Design advocate Michael Behe. But not to worry! After him, they have a parade of scientists who not only agree that Chuck Darwin basically had it right in 1859, but want to argue for that conclusion using ROBOTS! and MATH!
So, uh, that’s where I come in. My segment features me (or rather my animated doppelgänger, “SuperScott”) trying to color a chessboard two colors, so that no two neighboring squares are colored the same, using three different approaches: (1) an “intelligent design” approach (which computer scientists would call nondeterminism), (2) a brute-force, exhaustive enumeration approach, and (3) an “evolutionary local search” approach.
[Spoiler alert: SuperScott discovers that the local search approach, while not as efficient as intelligent design, is nevertheless much more efficient than brute-force search. And thus, he concludes, the arguments of the ID folks to the effect of “I can’t see a cleverer way to do it, therefore it must be either brute-force search or else miraculous nondeterminism” are invalid.]
Since my appearance together with Morgan Freeman on cable TV raises a large number of questions, I’ve decided to field a few of them in the following FAQ.
Q: How can I watch?
Amazon Instant Video has the episode here for $1.99. (No doubt you can also find it on various filesharing sites, but let it be known that I’d never condone such nefarious activity.) My segment is roughly from 10:40 until 17:40.
Q: Given that you’re not a biologist, and that your research has basically nothing to do with evolution, why did they ask to interview you?
Apparently they wanted a mathematician or computer scientist who also had some experience spouting about Big Ideas. So they first asked Greg Chaitin, but Chaitin couldn’t do it and suggested me instead.
Q: Given how little relevant expertise you have, why did you agree to be interviewed?
To be honest, I was extremely conflicted. I kept saying, “Why don’t you interview a biologist? Or at least a computational biologist, or someone who studies genetic algorithms?” They replied that they did have more bio-oriented people on the show, but they also wanted me to provide a “mathematical” perspective. So, I consulted with friends like Sean Carroll, who’s appeared on Through the Wormhole numerous times. And after reflection, I decided that I do have a way to explain a central conceptual point about algorithms, complexity, and the amount of time needed for natural selection—a point that, while hardly “novel,” is something that many laypeople might not have seen before and that might interest them. Also, as an additional argument in favor of appearing, MORGAN FREEMAN!
So I agreed to do it, but only under two conditions:
(1) At least one person with a biology background would also appear on the show, to refute the arguments of intelligent design.
(2) I would talk only about stuff that I actually understood, like the ability of local search algorithms to avoid the need for brute-force search.
I’ll let you judge for yourself to what extent these conditions were fulfilled.
Q: Did you get to meet Morgan Freeman?
Alas, no. But at least I got to hear him refer repeatedly to “SuperScott” on TV.
Q: What was the shooting like?
Extremely interesting. I know more now about TV production than I did before!
It was a continuing negotiation: they kept wanting to say that I was “on a quest to mathematically prove evolution” (or something like that), and I kept telling them they weren’t allowed to say that, or anything else that would give the misleading impression that what I was saying was either original or directly related to my research. I also had a long discussion about the P vs. NP problem, which got cut for lack of time (now P and NP are only shown on the whiteboard). On the other hand, the crew was extremely accommodating: they really wanted to do a good job and to get things right.
The most amusing tidbit: I knew that local search would take O(n4) time to 2-color an nxn chessboard (2-coloring being a special case of 2SAT, to which Schöning’s algorithm applies), but I didn’t know the constant. So I wrote a program to get the specific number of steps when n=8 (it’s about 5000). I then repeatedly modified and reran the program during the taping, as we slightly changed what we were talking about. It was the first coding I’d done in a while.
Q: How much of the segment was your idea, and how much was theirs?
The chessboard was my idea, but the “SuperScott” bit was theirs. Luddite that I am, I was just going to get down on hands and knees and move apples and oranges around on the chessboard myself.
Also, they wanted me to speak in front of a church in Boston, to make a point about how many people believe that God created the universe. I nixed that idea and said, why not just do the whole shoot in the Stata Center? I mean, MIT spent $300 million just to make the building where I work as “visually arresting” as possible—at the expense of navigability, leakage-resilience, and all sorts of other criteria—so why not take advantage of it? Plus, that way I’ll be able to crack a joke about how Stata actually looks like it was created by that favorite creationist strawman, a tornado passing through a junkyard.
Needless to say, all the stuff with me drawing complexity class inclusion diagrams on the whiteboard, reading my and Alex Arkhipov’s linear-optics paper, walking around outside with an umbrella, lifting the umbrella to face the camera dramatically—that was all just the crew telling me what to do. (Well, OK, they didn’t tell me what to write on the whiteboard or view on my computer, just that it should be something sciencey. And the umbrella thing wasn’t planned: it really just happened to be raining that day.)
Q: Don’t you realize that not a word of what you said was new—indeed, that all you did was to translate the logic of natural selection, which Darwin understood in 1859, into algorithms and complexity language?
Yes, of course, and I’m sorry if the show gave anyone the impression otherwise. I repeatedly begged them not to claim newness or originality for anything I was saying. On the other hand, one shouldn’t make the mistake of assuming that what’s obvious to nerds who read science blogs is obvious to everyone else: I know for a fact that it isn’t.
Q: Don’t you understand that you can’t “prove” mathematically that evolution by natural selection is really what happened in Nature?
Of course! You can’t even prove mathematically that bears crap in the woods (unless crapping in the woods were taken as part of the definition of bears). To the writers’ credit, they did have Morgan Freeman explain that I wasn’t claiming to have “proved” evolution. Personally, I wish Freeman had gone even further—to say that, at present, we don’t even have mathematical theories that would explain from first principles why 4 billion years is a “reasonable” amount of time for natural selection to have gotten from the primordial soup to humans and other complex life, whereas (say) 40 million years is not a reasonable amount. One could imagine such theories, but we don’t really have any. What we do have is (a) the observed fact that evolution did happen in 4 billion years, and (b) the theory of natural selection, which explains in great detail why one’s initial intuition—that such evolution can’t possibly have happened by “blind, chance natural processes” alone—is devoid of force.
Q: Watching yourself presented in such a goony way—scribbling Complicated Math Stuff on a whiteboard, turning dramatically toward the camera, etc. etc.—didn’t you feel silly?
Some of it is silly, no two ways about it! On the other hand, I feel satisfied that I got across at least one correct and important scientific point to hundreds of thousands of people. And that, one might argue, is sufficiently worthwhile that it should outweigh any embarrassment about how goofy I look.
Follow
Comment #1 August 5th, 2013 at 12:52 pm
That must give you a pretty competitive Erdos-Bacon number.
Comment #2 August 5th, 2013 at 1:04 pm
Joe: Dude, THANKS, I hadn’t even considered that! My Erdos-Bacon number is now 5:
Me → Andris Ambainis → Leonard Schulman → Paul Erdos (and many other equal-length paths),
Me → Morgan Freeman → Kevin Bacon.
How amusing that my path to Kevin Bacon is now shorter than my path to Erdos!
Comment #3 August 5th, 2013 at 1:23 pm
Was the shoot in LA?
Comment #4 August 5th, 2013 at 1:27 pm
No, they sent a crew to Boston, and we shot in the building where I work, the Stata Center (over the weekend, when there were fewer people around).
Comment #5 August 5th, 2013 at 2:42 pm
Now you need to work on your Erdos-Bacon-Sabbath number.
Comment #6 August 5th, 2013 at 3:24 pm
I thought you did a fine job and explained the concepts you wanted to get across quite well. I learned something new and thanks for that. However, the show is far too comfortable trafficking in pseudoscience. Opening with Behe and the roundly discredited idea of irreducible complexity makes the point. Robots and maths are not adequate refutations of intelligent design and leave the viewer with the idea that there is a disconnect with the natural world.
I understand that the producers of the show must make it accessible to the widest possible audience but at what cost? There are some things that science actually has a good handle on and evolutionary theory is one of them.
Comment #7 August 5th, 2013 at 3:47 pm
Michael T: Thanks for your comment. I also would’ve strongly preferred if they’d put a “straight” evolutionary biologist on the show, to refute Behe’s claims about irreducible complexity directly. In fact, I suggested that to them many times.
However, they seemed dead-set on having the episode focus on “new perspectives” about evolution (so, on one side of the ring: ID! and on the other side: ROBOTS! MATH! HIGHER-LEVEL LAWS OF COMPLEXITY!) I guess the perspective that the neo-Darwinian synthesis remains perfectly fine wasn’t exciting enough for the Science Channel. So, given that, the question is: what do I do? Do I decline to participate, or do I simply do my best to explain Darwin’s great insight (from my own perspective as a math/CS person), and thereby move the show in what I think is the right direction? I chose the latter, though I wouldn’t blame someone else for declining.
Comment #8 August 5th, 2013 at 5:50 pm
It is vitally important that scientists of your caliber weigh in on these types of shows. You do us all a great service. Your suggestion for the show to dismiss Behe’s claims did in fact fall on deaf ears unfortunately as it would have alienated many viewers. This is precisely why I am not a television producer 🙂
If I was to be so bold as to make a suggestion, perhaps first reviewing past episodes would give you a better idea as to the intent of the producers. An example in the extreme and a cautionary tale is what happened to David Albert in the film “What the Bleep”. Regardless of how careful he was in his explanations of the quantum world on camera, selective editing was enough to twist its meaning.
I must add though, to frame ID as a “new perspective” about evolution would have been enough for me to head for the hills.
Comment #9 August 5th, 2013 at 6:39 pm
Michael T: I see each 10-minute part as a nearly self-contained short movie. It looks like Scott had enough control of his own part to make it enjoyable and as correct as possible. I loved it! As for the whole episode, I even enjoyed ID part, because it created something to argue with in later parts. Robots were great too.
Comment #10 August 5th, 2013 at 6:55 pm
Michael #8: I did review past episodes—mostly on long transatlantic flights where they had it on the menu! When I did, I was pleasantly surprised to find Sean Carroll and some of my other friends speaking to me, more-or-less as if they were in the seat next to me.
Anyway, watching the past episodes is what convinced me that the producers of Wormhole were fundamentally well-intentioned, even if more ready than I’d be to give airtime to some extremely flaky ideas (I don’t mean Sean Carroll’s, of course 🙂 ). In that sense, it seemed completely different from What the Bleep, which had a slimy/dishonest/huckster motive at its core, and wasn’t at all interested in accurately explaining anything.
Comment #11 August 5th, 2013 at 8:51 pm
Walksat has never been taken so literally before.
Comment #12 August 5th, 2013 at 10:03 pm
Can you give a good example of a problem where “local search” beats “intelligent design”? Of course, it is easy to construct problems for which a local search algorithm, running on a modern digital computer, easily beats the best solution that most humans would find without computer assistance. But, can you construct a family of problems that a typical intelligent person could not solve in a reasonable time, but that they could rapidly solve if you told them to follow a local search rule? Of course, I’m assuming that the “typical intelligent person” doesn’t guess in advance to follow a local search rule before you tell them, but given that the algorithm you cite was presented in a premier CS conference less than 20 years ago, I would hope that it isn’t a result that is obvious to most people.
Comment #13 August 5th, 2013 at 10:35 pm
matt #12:
can you construct a family of problems that a typical intelligent person could not solve in a reasonable time, but that they could rapidly solve if you told them to follow a local search rule?
I think so, yes. How about, let’s say, the problem of constructing a de Bruijn sequence: e.g., a circular string of 64 bits in which every 6-bit substring is different. Pretty tricky if you try to do it in a “principled” way—but, if memory from programming competitions ~15 years ago serves correctly, a local search algorithm converges on a solution rapidly.
Comment #14 August 6th, 2013 at 2:03 am
Matt, reasonably intelligent people tend to instinctively try stochastic algorithms before going to exhaustive ones. In fact people who aren’t programmers or mathematicians tend to have trouble wrapping their brains around exhaustive search at all. Most packing problems are much better solved with stochastic search. N queens is another example. In both of those the advantage of stochastic is very obvious to anyone who tries doing them.
Comment #15 August 6th, 2013 at 8:37 am
Bram #14: Yeah, I also noticed that issue with Matt’s question! Why wouldn’t the “typical intelligent person” simply converge on local search before long? So, that’s why I tried to come up with an example where the “typical intelligent person” might be misled into looking for an elegant/symmetric/principled solution, when they should really just be doing local search.
Comment #16 August 6th, 2013 at 9:13 am
You did a nice job showing the power of local search in general, but your example does not rebut Behe’s claims directly.
I assume you agree that there are SOME solutions that local search algorithms do a bad job finding (i.e. are “irreducibly complex”). Then the relevant question is whether observed biological structures are members of this class.
My understanding is that biologists have shown that many cases that appear irreducibly complex are actually not. This seems the right approach if you’re concerned with refuting Behe in particular.
(For context: I’m someone who found ID appealing when I was in high school, but ten years later fully accepts evolution)
Comment #17 August 6th, 2013 at 9:55 am
ramsey #16: Yes, I completely agree. Two-coloring a graph is a special case of 2SAT, which is known to be in P—which helps to explain why a simple local search heuristic not only gets to the optimum in polynomial time, but does so provably. In some sense, if P≠NP then there have to be “irreducibly complex” problems, for which all local search heuristics fail! So then you then have to delve into the details of biology, to figure out how local search could have possibly found these particular solutions (the eye, the wing, etc.) in reasonable amounts of time.
Now, suppose that, in every single case that you examine in enough detail—including cases that had been confidently put forward as “irreducibly complex”—you do discover a path by which local search could have worked, and by which it apparently did work. Then that might give you enough confidence to conjecture that, even in those cases where you haven’t yet figured out a local search path, there probably is one. Especially so if the only alternative explanation on offer is, “well, maybe the solution just miraculously appeared”! That, in essence, is the real answer to Behe.
I did explain some of the above in the “P vs. NP” portion of my interview, which was unfortunately cut for lack of time.
However, I would also add that, at least in my experience, most people who say they’re skeptical of evolution don’t even get to the point of having the above discussion. For most people, it’s a simple matter of:
I don’t see how it could’ve been done (except perhaps via brute-force search). And therefore, if we rule out brute-force search, then it can only have been a miraculous act of God.
And for such people, I’d say that the local search solution to 2-coloring—or for that matter, any nontrivial polynomial-time algorithm, for any problem someone might have thought would require exponential time—is a sufficient refutation.
Comment #18 August 6th, 2013 at 11:32 am
At one time it was my hope that Behe’s Irred Complexity,
and some of the gaps in the fossil record would lead to interesting insights (e.g., Gould’s Puntuated equilibrium).
But having read some books by ID people my impression is that they use these things as window dressing (e.g.,
Therefore Darwin is wrong) rather than points of departure
for interesting studies (e.g., Therefore evolution doesn’t quite
explain this, so lets study it further and see where it leads,
perhaps to a modification of Evol, perhaps to a new theory.)
I would welcome an intelligent intelligent design community that does experiments and looks at the fossil record and other stuff with a skeptical point of view, but is willing to go where the evidence leads. But alas that does not seem to be the case.
So is there anything interesting to be found there?
Have evol scientists looked? I don’t know.
One thing particularly daming- Evolutions have had creationsis and ID people at their conference, but
Evolutions are banned from creationist and ID conferences.
Comment #19 August 6th, 2013 at 12:59 pm
GASARCH, http://arxiv.org/abs/1304.3381v1 might be of interest.
It says there appears to be a biological version of Moore’s Law, that genetic complexity seems to double every ~376 million years, per this article:
http://www.technologyreview.com/view/513781/moores-law-and-the-origin-of-life/
That would explain why it took N billion years to get where we are. In fact that particular paper says 4 billion wasn’t enough…
Comment #20 August 6th, 2013 at 1:45 pm
Also necessary to the stable sustainment of complexity-in-biology are Nature’s vastly intricate DNA repair mechanisms.
A rule-of-thumb is that nearer to quantum limits that an information storage mechanism approaches, the more sophisticated and intricate its error-correction mechanisms become. Examples include:
• mechanical latch no error correction needed
• computer RAM SECDED circuits suffice
• DNA typically 30+ repair mechanisms
• qudits scalable error correction problematic
Similar considerations apply generically to the many dynamical processes that act to reduce biology entropy (e.g, DNA replication, tissue synthesis, neural learning), needless to say!
There are some biologists who believe that the complexity of mammalian biology is fundamentally limited, not by the efficacy of macroscopic Darwinian evolution, but by our finite ability to repair the thousands of DNA lesions that every cell accumulates every day.
Summary It is plausible that we mammals have already evolved to be about as complicated as any (thermally hot, chemically error-prone) DNA-based organism can be.
Comment #21 August 6th, 2013 at 2:31 pm
Local search is not always optimal. How do you know the landscape of solutions that evolution went through is similar to landscape of solutions similar to 2-SAT? Isn’t providing this piece of information to the general populace scientific misconduct?
Comment #22 August 6th, 2013 at 2:32 pm
Should be “Isn’t not providing that piece of information….”.
Comment #23 August 6th, 2013 at 2:52 pm
QuestionMan: Local search doesn’t need to be “optimal”; it just has to get to a good enough solution in a reasonable amount of time.
I don’t know that the landscape of solutions for real biology looks anything like the landscape for 2SAT: indeed, as I said already in comment #17, it’s obviously much more complicated and harder to navigate, full of local optima and so on. All I was claiming to do in this segment, and all I did do, was to refute the ID-inspired misconception that if you can’t see how to find something more quickly than by brute-force search, then ipso facto that thing is “irreducibly complex.” And for refuting that general error, a single counterexample suffices.
I tried hard to make my segment as accurate as I could, within the severe constraints I was operating under (7 minutes total; anything too subtle or complicated will get edited out; the least careful sentence out of your mouth will inevitably be the sentence they highlight). And I’m reasonably happy with the result. Yet, even if I had been a lot sloppier, it still wouldn’t have been “scientific misconduct,” a phrase normally reserved for plagiarism and fraud.
Comment #24 August 6th, 2013 at 3:41 pm
Don’t take QuestionMan’s comment personally Scott — the guy obviously suffers from SMSD — Scientific Misconduct Surplus Disorder. It’s common among a certain type. They are looking for Scientific Misconduct in all the wrong places. 😉
Comment #25 August 6th, 2013 at 3:48 pm
Scott, doesn’t Walksat on 2SAT require average case quadratic flips? If we look at the value of the minimum number of flips necessary to get to a solved state, then with every flip the chances of that number decreasing are at least 1/2, so worst case scenario it goes up half the time and down half the time, and the average amount of time it takes a thing to go a given distance in a random walk on a straight line is quadratic.
Comment #26 August 6th, 2013 at 4:39 pm
Bram #25: Yes, that’s exactly right. There are 2n(n-1) color constraints for an nxn chessboard, so quadratic time = O((2n(n-1))2) = O(n4).
Comment #27 August 6th, 2013 at 5:34 pm
Professor: Thankyou for the detailed comments. My mistake in not looking at earlier comments. However in all humbleness your effort is worthless then. I am sure there are ‘logically’ sensible ID supporters who have seen through efficient algorithms for workable problems. As you are claiming your effort cannot convince those folks. Anyways you can only go so far in 7 minutes. I am unsure what else could be thought off to convince those folks even if you had more time and more intellectual leeway to go deeper in the program.
Comment #28 August 6th, 2013 at 5:35 pm
” Yet, even if I had been a lot sloppier, it still wouldn’t have been “scientific misconduct,””
Sorry my mistake for the choice of words there.
Comment #29 August 6th, 2013 at 6:34 pm
QuestionMan #27:
your effort is worthless then. I am sure there are ‘logically’ sensible ID supporters who have seen through efficient algorithms for workable problems.
At least in my experience, the majority of ID proponents really, genuinely don’t understand that there’s an efficiency difference between natural selection and brute-force search. They see both of them as “blind, chance processes,” and (as such) completely interchangeable with one another.
Your argument seems to be that it’s “worthless” to try to explain to those people what natural selection is all about, since there exist some people who understand natural selection correctly but nevertheless reject it.
In the same way, one might argue, if a guy meets a single girl who “understands” him but still doesn’t want to date him, then there’s no point in his asking anyone out ever again. Or, if a blogger encounters a single commenter who understands his post but still disagrees with it, then he’d better devote his entire life to winning that commenter over … since until he does, no reaction by any other reader “counts.”
Hey, some of this is hitting uncomfortably close to home… 😉
Comment #30 August 6th, 2013 at 7:23 pm
“Or, if a blogger encounters a single commenter who understands his post but still disagrees with it, then he’d better devote his entire life to winning that commenter over … since until he does, no reaction by any other reader “counts.””
Shameless to say: I do not understand natural selection completely except for the idea of it (I would bet no does correctly). My intuition is if I did understand it, I would be in a better position to explain those folks I have been mentioning.
I lost the link to a website which talks about statistical fluke in time series, Godel’s incompleteness (and an application to global warming which the blog asserts exists). More or less, the moral came out to be there are some strings of time series which have no explanation naturally. I would really like to connect this explanation to origin of life and argue from a view point of an ID but since I dont have the blog with me my small brain cannot connect the dots. My view point is somethings cannot be explained succinctly. If they wish to explain using ID or natural selection both are equally wrong (more like the view point of the ancients thinking the earth was flat – but hey according to Asimov it worked for close to 2000-3000 years pretty well for navigational purposes – just like natural selection has explained many things so far just like blind faith in fairies).
Comment #31 August 7th, 2013 at 7:33 am
The notion that the ancients, or that people in Columbus’s
day thought the Earth was flat is a Myth. There is a good book on this `The Flat Earth Myth’ and also a good Wikipedia entry on `Myth of the Flat Earth’
Its a hard myth to kill since (1) Liberals like that Columbus was going AGAINST the establishment, and (2) Conservatives like that Columbus was a HERO. Columbus seems to have
fallen out of favor (not much of a celebration in 1992) because of his treatment of the Native Americans, but the flat earth myth persists.
Comment #32 August 7th, 2013 at 7:44 am
QuestionMan —
My understanding is that natural selection can be expressed succinctly (i.e. mathematically), and that these expressions make non-trivial predictions about things like mutation rates in genetic code that match what we observe in reality.
Comment #33 August 7th, 2013 at 11:58 am
$non-trivial \neq exact$
Comment #34 August 7th, 2013 at 12:00 pm
well I take my words back again. $non-trivial$ is not sufficient for most purposes such as abiogenesis of life.
Comment #35 August 7th, 2013 at 6:02 pm
Scott, thank you for making the effort. I despise ID and can’t stand the proselytizers of this pseudo science. One random ID adherent once came upon me while I was hiking the Grand Canyon, and he had nothing better to do than to ruin the experience for me. Without prompting, trying to impress the point on me that the landscapes beauty was clear evidence for ID. Obnoxious people.
Comment #36 August 8th, 2013 at 5:02 am
@Henning Dekant:
Your annoyance puzzles me, but I’ve heard others express similar sentiments. If I came across someone trying to convince me,say, that doomsday was in 2015 I’d be more amused than annoyed. Sometimes in this whole ID vs Evolution debate I find fanaticism on both sides.
It’s like wondering: Would my experience of watching a beautiful full moon be ruined by someone insisting it’s really made of swiss cheese?
Comment #37 August 8th, 2013 at 5:18 am
Scott posts “The arguments of the ID folks to the effect of ‘I can’t see a cleverer way to do it, therefore it must be either brute-force search or else miraculous nondeterminism’ are invalid.”
—————————————-
Scott, your strong arguments against ID map onto comparably strong argments against strict quantum constructionism. David Deutsch’s lively expression of strict quantum constructionism is:
Your argument against ID transposes (in effect) to an argument against strict quantum constructionism
To express this notion another way, if it is true that Nature’s evolutionary dynamics looks locally like ID but globally isn’t, then perhaps it is true too that Nature’s thermodynamics looks locally like a unitary flow on a flat Hilbert space but globally isn’t.
Conclusion Broader/deeper/more natural mathematical understanding is helping 21st century STEM researchers to escape the dual cognitive strait-jackets of ID and flat Hilbert space. That is good news for young STEM researchers! 🙂
Comment #38 August 8th, 2013 at 5:23 am
Rahul #36: Suppose there existed a movement, embraced by one of America’s two major political parties, that insisted that the moon was made of swiss cheese (and moreover, that the belief in a swiss-cheese moon was essential for a moral society). Suppose this movement had actually got its teachings into schools and textbooks, wherever and whenever it had enough power to. Suppose roughly half of Americans agreed with it (or at least were on the fence). In that case, sure, I could easily imagine that someone insisting the moon was made of swiss cheese might ruin the experience of a beautiful moon for me.
Comment #39 August 8th, 2013 at 10:16 am
Scott #36:
Fair enough. As a public policy matter, yes it is a serious annoyance. For a public intellectual too, ditto.
I just don’t see it annoying me on a random personal interaction level (again keeping in mind the high threshold of other questionable beliefs people maintain, a lot of which are more immediately harmful than a crackpot belief in ID)
Also, in @Henning’s example the moral for me is: There’s a right place for everything. Proselytizing to someone trying to take in the breathtaking beauty of Grand Canyon is in itself annoying. I don’t think the specifics of whether the proselytizer is on the right side or wrong matters.
I’d be as annoyed of someone trying to tell me there that the war in Iraq was wrong or GM-crops are evil or eating locally grown organic foods is virtuous.
Comment #40 August 8th, 2013 at 11:20 am
John Sidles #37: I have my own quibbles with Deutsch’s MWIism, but I think your analogy fails for the following reason. In the case of evolution, we can give examples—thousands of them, actually—where it’s not intuitively clear how something could’ve possibly evolved by natural selection, and yet biologists know in great detail how it did evolve. Those examples are what give us the confidence to conjecture that natural selection could’ve worked even in those cases where we don’t yet know the selection path.
But I know of no similar evidence that it’s possible to modify QM and get a theory that’s also sensible and also agrees with experiments. (Of course, one problem is that we don’t know anything else particularly “like” QM—with the possible exception of classical probability theory, which is also extremely hard to modify.) So here it really is just one person’s intuition against another’s.
Sure, maybe it’s possible to modify QM to some other sensible theory—the question is obviously important, and in fact it’s motivated a lot of my research. But I don’t think serious discussion of the question even really starts, until there’s a more specific proposal on the table for how to modify QM, or at least for where QM should break down.
Comment #41 August 8th, 2013 at 11:28 am
Rahul #39: I, too, can certainly get annoyed even by annoying people on the “right” side. (For example, if I donate money to some liberal cause, and then they call me every day asking for additional donations, I might starting hating their guts, and resolve not to give them another cent even if I would’ve done so otherwise.) But annoying people who are also dead wrong annoy me even more! 🙂
Comment #42 August 8th, 2013 at 11:49 am
Scott #41:
Six years in a University Town and the sight I came to dread most was a pair of well-dressed, young men in conservative suits coming walking towards me on the sidewalk on a Sunday morning. I often scurried across to the other side of the street too, timid me.
Comment #43 August 8th, 2013 at 3:47 pm
Hi Scott,
I just discovered this blog, and I really enjoy it. I went to school for Violin and Music Theory, but as I’ve gotten older I find myself increasingly interested in sciences. I have a general question about how to go about learning more about the topic (and yes, I am aware of the links on your home page :)) in a structured way.
One of the thing I learned studying Music Theory is the devastating necessity of obtaining a mastery of the fundamental skills to achieve bigger-picture insights. If you have to consciously think about how to spell a given chord or think a lot about the rules of some given contrapuntal system, you are going to have trouble seeing beyond that and generating high-level insights.
So when I set about changing careers from a violinist to a statistician, I took the same approach. Do the exercise problems until you almost don’t have to think about the fundamentals anymore, then move onward and upward. And that worked pretty well. I’m now a software engineer that writes statistical applications.
I’m interested enough in the philosophical implications of what I’m reading here that I want to embark on a multi-year mission to understand this at a level that would allow me to participate intelligently in the conversation.
I think the first response might be to go back to school if I want to learn it that badly. But I don’t really enjoy universities. They don’t fit well with my learning methods. No offense intended (seriously, I don’t mean to insult anyone. both my parents are university professors.)
So my question is this: what maths would you say are fundamental to understanding computational complexity theory? What list of fields should I approach and develop a mastery of before moving on?
Thanks!
-andrew
Comment #44 August 8th, 2013 at 4:17 pm
AndrewM #43:
what maths would you say are fundamental to understanding computational complexity theory?
Basic probability theory and statistics, basic combinatorics and graph theory, basic abstract algebra (especially finite groups and finite fields), basic number theory, and linear algebra. Depending on what part of computational complexity you’re interested in, logic, numerical analysis, geometry, approximation theory, or even topology (esp. fixed-point theorems) or representation theory could be relevant.
On the one hand, there’s hardly any area of math that has no application to computational complexity. But on the other hand (and partly because of that), far more important than knowing any particular area is being comfortable with mathematical thinking: how to clearly define what you’re talking about, formulate a conjecture, prove a theorem, search for a counterexample, find an easier version of an open problem, give a crude upper or lower bound, etc. Those things are relatively similar across almost all mathematical fields (including computational complexity).
Comment #45 August 8th, 2013 at 4:33 pm
Thanks for the reply. I have most of a Philosophy degree too, and my interest there is primarily in Logic. The more I continue to study logic, the more I end up pointed at Math. The mathematical thinking is really what I’m aimed at refining in my mind. I admire the clarity of doing what you’re talking about: defining problems, creating proofs, knowing very clearly what you know vs. what you don’t know.
Comment #46 August 8th, 2013 at 9:33 pm
Rahul #39: Scott pretty much touched on all the aspects why ID is more problematic than the cheese moon.
But really what it comes down for me is how I’d answer your question:
It’s like wondering: Would my experience of watching a beautiful full moon be ruined by someone insisting it’s really made of swiss cheese?
Yes, it’ll ruin it for me. Especially if this person is genuinely convinced of this absurd fact, and in my face about trying to convince me of this “truth”. There’s only so much stupid I can abide (which is why I’d probably make a horrible teacher).
Comment #47 August 9th, 2013 at 7:32 am
Hey Scott, when are you going to see a MOOC course from you ? Gee, that would be awesome.
Im really awaiting to see “QC since democritus” or “Great Ideas In Theorical Computer Science” or event better “6.045 Automata, Computability, and Complexity”.
I bet David Mermin’s words on Feynman classes applies to you: “I would drop everything to hear him (feynman) lecture on the municipal drainage system”.
I drop everything to hear one of your classes!!
Thanks
Julio
Comment #48 August 9th, 2013 at 1:20 pm
Julio #47: I’ve put in a request with EdX to teach my 6.045 course as a MOOC! But I don’t know when it’s going to happen—as you might know, EdX hasn’t been moving as quickly as Coursera or Udacity, and right now (as I understand it) has too few staff and too many courses to produce. Furthermore, this year I’m taking my paternity leave and then my sabbatical, so the soonest I could do it would be Spring 2015.
The main things I worry about are the following:
(1) The preferred format of MOOCs—with 7-minute video “chunks” that build on each other in a precisely-delineated way—is a very bad fit to the normal way I lecture. I like to tell stories and jokes, go off on digressions, interact with the class, etc. etc. I could probably learn to do it the “MOOC way,” but it would be a major adjustment for me.
(2) If I’m producing something for “posterity,” then I’m much more comfortable if it’s text than if it’s video of me talking. As you know if you’ve watched any of my talks on YouTube, I’m not at all a smooth, fluent, or media-trained speaker. Also, I never have the patience to watch video lectures myself, even though I constantly read and I don’t mind attending lectures in person. So, producing a MOOC would be producing something that I myself wouldn’t want to consume, which is always a tricky proposition.
(3) I’m still not sure how grading/evaluation should work in a theoretical computer science MOOC. I don’t want to use an automated proof-checking program—writing out machine-checkable proofs of computability/complexity theorems is likely to be extremely cumbersome, and at any rate it would make it a completely different course. I could just resort to multiple choice, but then students would finish the course with no experience proving theorems in theoretical computer science.
Despite all this, I’m sure I’ll do it eventually. In the meantime, there’s my book, the blog, the written lecture notes, and all the talks on YouTube. 🙂
Comment #49 February 8th, 2016 at 4:49 am
@Scott #48
I’ve lurked here a lot, but this is my first comment so I should probably mention at the outset how much I enjoyed Quantum Computing Since Democritus. It’s easily my favourite not-quite-textbook/popular-with-quotes science book.
It would be amazing to have 6.045 on edX. Regarding your reservations (1) and (2), there was a course I took, MIT’s Paradox and Infinity, where the video segments were optional (a full length lecture video was also made available, with the MOOC-like chunks cut from it alongside the text). I got through by reading the text only. (Incidentally, a lecture of yours featured as bonus material for the topic Computability.)
Towards addressing (3), on Coursera I took Stanford’s Automata course, where I felt the assessment was reasonably rigorous given that assessments were multiple choice. On edX at least you can enter simple mathematical expressions on top of this. I suppose this isn’t entirely satisfactory, but it’s a thought.
Comment #50 August 9th, 2013 at 3:50 pm
Scott #48 whatever you lack in being media trained you make up in being funny – the good kind – not the involuntary one 🙂
From what I’ve seen, you really have a great presence in front of the camera, even if it may feel awkward to you.
When I took the EdX quantum computing course it was mostly just to get a feel for how well this platform works and I was surprised how much I enjoyed it. Also found that it helps that they allow to play the video faster. It made Umesh sound like he inhaled Helium, but man, would I have loved to have this button in some lectures that I had to sit through.
Comment #51 August 9th, 2013 at 10:39 pm
…late to the party, just watched the episode on youtube, very nice! Thumbs up, Scott, and thank you ;-)!
Comment #52 August 9th, 2013 at 11:54 pm
Regarding MOOC’s in general:
Teachers should focus on coming up with a better credentialing model. Right now lot’s of people can write that they sat through MOOC-X but it’s really really hard to know who actually learnt anything from it.
I hope Scott can come up with something novel here.
Comment #53 August 10th, 2013 at 1:38 am
Rahul #51, certainly wouldn’t claim that I learned much QC or QM ‘sitting through’ the EdX quantum computing course, as I already had QM on a graduate level.
To me it was mostly curiosity about the format, I was surprised to find that just as some people look forward to the NYT crossword puzzles, I got quite addicted to the weekly assignments. They really were fun brain teasers. I thought Umesh and his team did a great job putting them together. For some reason, to me it was just more fun to get the instant solver feedback then to just work through a problem from a textbook. Can’t quite put my finger on it, probably just the instant gratification loop kicking in, that our brains are hardwired to.
At any rate, if you look at the statistics for this course it is quite obvious that many who started found they couldn’t just sit through it.
You still have to work the assignments and pass the exams which at least required some comfort level with linear algebra (which was listed as prereq).
For whatever reason, only about a third of those who submitted the first assignment made it to the midterm.
Comment #54 August 10th, 2013 at 3:07 am
@Henning #52:
Sorry, I wasn’t criticizing your MOOC experience. In hindsight it may look like that. Apologies.
For the things you described (curiosity about the format, fun brain teasers, instant gratification etc.) I think MOOCs perform awesomely.
The worry / skepticism I have is about enthusiasts who see MOOCs as supplanting / competing with the traditional university courses model. I don’t see that happening yet, and IMHO lack of sufficient credentialing is a big part of that.
Online courses are great at reaching out to the wider public, or casual learners etc. but the fraction who’s willing to pay money (for the non-free versions) or to bank on MOOCs as a serious professional qualification in exceedingly small, I think.
Comment #55 August 10th, 2013 at 1:28 pm
Scott, you’ve inspired me to do something you might think is silly. But I’m actually going to take this topic and try to understand it seriously. I’ll be keeping track of what is going on here: http://www.veryniceresearch.com/
It’s a janky wordpress site, and since I’m a tinkerer I’ll be messing with things and probably just build what I want in python anyway. So who knows what you will get when click through.
But thanks for being such an accessible guy and not blowing me off.
Comment #56 August 10th, 2013 at 1:46 pm
In the version of Behe’s argument I last saw, it stated that single-codon errors in DNA transcription could not generate genomes of the length and complexity exhibited by known species in the time provided by Earth’s known age, and therefore the neo-Darwinian synthesis’ claim that the species arose by that means must be false. The distinction between brute force exhaustive enumeration and local search isn’t relevant to that argument at all. It isn’t a matter of “how long would it take monkeys pounding on typewriters to produce a copy of the plays of Shakespeare”; it’s more like “how long would it take a human being to convert a copy of the plays of Shakespeare into a copy of The Lord of the Rings by adding, deleting or replacing one letter at a time – without, at any point, turning the text into gibberish”.
The real mistake in Behe’s argument is that genetic mutation isn’t limited to single-codon errors. Whole “paragraphs”, blocks of thousands of codons, can be moved, copied or deleted in a single generation. This is in fact how the “irreducibly complex” systems ID exhibits as evidence against the neo-Darwinian synthesis actually arose; when researchers find such systems, they look for parts like the components elsewhere in the creature’s genome.
Comment #57 August 10th, 2013 at 11:55 pm
Rahul #53, no worries. Your point is well taken and reflects a common notion in academia when it comes to distance learning. On the other hand the University of London has 150 years of experience with it (took a decree of queen Victoria to get it started though).
The Open University also came into existence by royal charter, albeit much later. It is now the largest academic institution in the United Kingdom and produces some pretty solid research.
So I’d say there is definitely a market for it, and it seems to work if you do it right.
Comment #58 August 11th, 2013 at 10:51 am
@Henning:
Out of curiosity, do you know any academics who ended up doing great research whose primary degrees were products of distance education (at the open univ., the 150 year history at London Univ. or otherwise)?
Comment #59 August 11th, 2013 at 9:45 pm
Rahul #57, I guess it depends on your definition of great research.
Comment #60 August 11th, 2013 at 9:56 pm
Rahul, you can also look at some of the publications that come out of the Open University.
To me, ever since Linux showed up Minix, it seems from a practical standpoint there is very little that cannot be accomplished remotely.
Comment #61 August 13th, 2013 at 3:38 am
@19, asdf: I find any concept of a biological version of Moore’s Law rather hard to square with the fact that, as far as biologists can tell, there is absolutely no correaltion between genome size and phenotypic complexity. Onions famously have a genome about 5 times the size of humans, and they’re not even a particularly egregious outlier. There are amoebas swimming around out there with genomes that put the human one in the shade.
So that paper seems a little strange. They claim to be measuring ‘genomic complexity’ but it’s a big and open question in biology as to what that even means, and it certainly doesn’t seem to mean anything as simple as “how many base pairs do you have?” They say they measure it by counting what percentage of a given genome is functional but that is also a huge open question, as the recent furore around the ENCODE results shows.
Perhaps I’ve missed something, but it smells a bit fishy to me.
Comment #62 August 15th, 2013 at 10:10 pm
One glaring point of the episode was the lack of fossil evidence for the transitional forms going from cartilaginous invertebrates all the way up to and including mammals. Given evolution is true, would not any geologic layer be replete with transitional forms for any number of biological structures (not just the spinal column), even if punctuated equilibrium was in part correct. A simple mans observation!
Comment #63 August 16th, 2013 at 1:11 am
In #44 you wrote, Scott, that “on the other hand […], far more important than knowing any particular area is being comfortable with mathematical thinking: how to clearly define what you’re talking about, formulate a conjecture, prove a theorem, search for a counterexample, find an easier version of an open problem, give a crude upper or lower bound, etc”. I was instantly transported to a memory of Polya’s 1945 classic, “How to Solve It”. So, of course, I pulled my copy from the shelf and sure enough: it’s time I read it again. The similarities with Deutch’s arguments about “good explanations” are, I think, interesting. Thanks for the impetus!
Comment #64 September 3rd, 2013 at 5:31 pm
Compliment for Raymond Cuenen.
Amazing!
Comment #65 September 28th, 2014 at 11:47 pm
I extremely enjoyed the episode. Thanks for the pointer. By the way how does one code the intelligent designer?
Comment #66 January 27th, 2016 at 1:11 pm
I loved the episode. Thanks for the ariticle.