Exploring the Galaxy in 1 Month
In his book Is There Life on Other Worlds, Poul Anderson makes a point about how long it would take to explore the galaxy. The "isolation" argument is usually used to explain why we have not been visited by extra-terrestrial life, i.e. it would take so long that this can be taken as a reason that we have not encountered any aliens so far (to our knowledge). However, the argument contains a flaw, which is that the exploration, or the growth of knowledge about explored systems, is linear.
But the galaxy can be thought of as basically a big network, and search in this network could proceed in parallel. A swarm of Von Neumann self-replicating machines could do the trick. (A self-replicating machine uses locally available materials to produce an exact copy of itself). In fact, in his 2006 Hugo-award-winning book Spin, Robert Charles Wilson suggests exploring the galaxy by using a swarm of nanotechnology robots that self-replicate.
So I got to thinking about just how long this would take. Turns out it would take at most two months and probably closer to one month. Here's why.
By measuring the total amount of light in the galaxy and dividing by the estimated mass distribution, we can calculate the number of stars that are there in the galaxy. So, even though we cannot actually count them, a reasonable figure for the number of stars in the galaxy is roughly 100 billion (100,000,000,000). Some estimates go up as high as a trillion.
You would start with one robot, then have two, then four, then eight, and so on as each robot replicated and then those two robots spread to the next two stars. So your exploration would increase not linearly (n), or even exponentially (n^2), but geometrically (2^n).
So, how long would it take to explore 100 billion stars? 37 - 40 days.
2^37 = 137,438,953,472
2^40 = 1,099,511,627,776
Even if you allowed for significantly higher estimates, you still would only need a few more days because the territory explored is doubling at every step. Furthermore, there is no reason to start with just one robot. A small swarm of them would start us out on the "powers of 2" list at a higher value. The difficulty would be getting the robots to start in different places (presumably they would all start from Earth).
Now, of course, this is science fiction, and isn't meant to be taken at face value. In actuality, the galaxy is about 100,000 light years in diameter, and about 1,000 light years thick, so even if our nanobots traveled at the speed of light, it would take them at least that long to get to the other side of the galaxy. Nevertheless, my point here is that all previous estimates of galactic exploration need to be revised from linear calculations to geometric ones.
There is a lot more interesting speculation around this idea on the Wikipedia entry on Self-replicating spacecraft.