All of Scott_Aaronson's Comments + Replies

The Weighted Majority Algorithm

once you know what your probability distribution is...

I'd merely stress that that's an enormous "once." When you're writing a program (which, yes, I used to do), normally you have only the foggiest idea of what a typical input is going to be, yet you want the program to work anyway. This is not just a hypothetical worry, or something limited to cryptography: people have actually run into strange problems using pseudorandom generators for Monte Carlo simulations and hashing (see here for example, or Knuth vol 2).

Even so, intuition suggests it sh... (read more)

The Weighted Majority Algorithm

I'm not making any nonstandard claims about computational complexity, only siding with the minority "derandomize things" crowd

Note that I also enthusiastically belong to a "derandomize things" crowd! The difference is, I think derandomizing is hard work (sometimes possible and sometimes not), since I'm unwilling to treat the randomness of the problems the world throws at me on the same footing as randomness I generate myself in the course of solving those problems. (For those watching at home tonight, I hope the differences are now reasonably clear...)

Above-Average AI Scientists

When Scott Aaronson was 12 years old, he: "set myself the modest goal of writing a BASIC program that would pass the Turing Test by learning from experience and following Asimov's Three Laws of Robotics..."

As I think back on that episode, I realize that even at the time, I didn't really expect to succeed; I just wanted to see how far I could get and what would happen if I tried. And it's not clear to me in retrospect that it wasn't worth a day's work: at the least, I learned something about how to write tokenizers and user interfaces! Certainly... (read more)

How An Algorithm Feels From Inside

While "reifying the internal nodes" must indeed be counted as one of the great design flaws of the human brain, I think the recognition of this flaw and the attempt to fight it are as old as history. How many jokes, folk sayings, literary quotations, etc. are based around this one flaw? "in name only," "looks like a duck, quacks like a duck," "by their fruits shall ye know them," "a rose by any other name"... Of course, there wouldn't be all these sayings if people didn't keep confusing labels with obse... (read more)

6Amanojack12y
Exactly. People merely need to keep in mind that words are not the concepts they represent. This is certainly not impossible, but - like all aspects of being rational - it's harder than it sounds.
Rationality Quotes 5

Are there any witticisms that don't count as 'rationality quotes'?

Natural Selection's Speed Limit and Complexity Bound

So here's my question: Can you actually do asymptotically better than natural natural selection by applying an error-correcting code that doesn't hamper beneficial mutations?

In principle, yes. In a given generation, all we want is a mutation rate that's nonzero, but below the rate that natural selection can correct. That way we can maintain a steady state indefinitely (if we're indeed at a local optimum), but still give beneficial mutations a chance to take over.

Now with DNA, the mutation rate is fixed at ~10^-8. Since we need to be able to weed out bad... (read more)

Natural Selection's Speed Limit and Complexity Bound

Wiseman, let M be the number of "functional" base pairs that get mutated per generation, and let C be the number of those base pairs that natural selection can affect per generation. Then if M>>C, the problem is that the base pairs will become mostly (though not entirely) random junk, regardless of what natural selection does. This is a point about random walks that has nothing to do with biology.

To illustrate, suppose we have an n-bit string. At every time step, we can change one of the bits to anything we want, but then two bits get ch... (read more)

Natural Selection's Speed Limit and Complexity Bound

Wiseman, if it's true that (1) copying DNA inherently incurs a 10^-8 probability of error per base pair, and that (2) evolution hasn't invented any von-Neumann-type error-correction mechanism, then all the objections raised by you and others (and by me, earlier!) are irrelevant.

In particular, it doesn't matter how capable a species is of coping with a few detrimental mutations. For if the mutation rate is higher than what natural selection can correct, the species will just keep on mutating, from one generation to the next, until the mutations finally do ... (read more)

Natural Selection's Speed Limit and Complexity Bound

Eliezer, sorry for spamming, but I think I finally understand what you were getting at.

Von Neumann showed in the 50's that there's no in-principle limit to how big a computer one can build: even if some fraction p of the bits get corrupted at every time step, as long as p is smaller than some threshold one can use a hierarchical error-correcting code to correct the errors faster than they happen. Today we know that the same is true even for quantum computers.

What you're saying -- correct me if I'm wrong -- is that biological evolution never discovered thi... (read more)

Natural Selection's Speed Limit and Complexity Bound

OK, I posted the following update to my blog entry:

Rereading the last few paragraphs of Eliezer's post, I see that he actually argues for his central claim -- that the human genome can’t contain more than 25MB of "meaningful DNA" -- on different (and much stronger) grounds than I thought! My apologies for not reading more carefully.

In particular, the argument has nothing to do with the number of generations since the dawn of time, and instead deals with the maximum number of DNA bases that can be simultaneously protected, in steady state, against... (read more)

Natural Selection's Speed Limit and Complexity Bound

OK, I came up with a concrete problem whose solution would (I think) tell us something about whether Eliezer's argument can actually work, assuming a certain stylized set of primitive operations available to DNA: insertion, deletion, copying, and reversal. See here if you're interested.

Natural Selection's Speed Limit and Complexity Bound

Eliezer, so long an organism's fitness depends on interactions between many different base pairs, the effect can be as if some of the base pairs are logically determined by others.

Also, unless I'm mistaken there are some logical operations that the genome can perform: copying, transpositions, reversals...

To illustrate, suppose (as apparently happens) a particular DNA stretch occurs over and over with variations: sometimes forwards and sometimes backwards, sometimes with 10% of the base pairs changed, sometimes chopped in half and sometimes appended to anot... (read more)

Natural Selection's Speed Limit and Complexity Bound

Eliezer, your argument seems to confuse two different senses of information. You first define "bit" as "the ability to eliminate half the possibilities" -- in which case, yes, if every organism has O(1) children then the logical "speed limit on evolution" is O(1) bits per generation.

But you then conclude that "the meaningful DNA specifying a human must fit into at most 25 megabytes" -- and more concretely, that "it is an excellent bet that nearly all the DNA which appears to be junk, really is junk." I do... (read more)

The Virtue of Narrowness

Eliezer: Excellent post, but I wonder if what you're saying is related to impressionist painting or the French Revolution? :-)

Seriously, I constantly meet people who ask me questions like: "could quantum algorithms have implications for biomechanical systems?" Or "could neural nets provide insight to the P versus NP problem?" And I struggle to get across to them what you've articulated so clearly here: that part of being a successful researcher is figuring out what isn't related to what else.

0ChristianKl10y
The answer to both "could-questions" is yes. People who work on the theory of neural nets have created a lot of mathematical theorems. It's plausible that some of those theorems are helpful when you want to solve P versus NP. Econophysics is a fairly established field. I think everyone involved understands that money is something different than atoms who interact with other atoms. That doesn't invalidate the field of Econophysics. You can make a pretty decent living as scientifist by using insight generated in field A to solve the problems of field B. Research into quantum algorithms is likely to produce knowledge that's useful for people who work in other fields such as biomechanical systems.