March 29th, 2008
Tomas Rokicki has written up a proof that any Rubik’s Cube configuration can be solved in 25 or fewer moves. In his paper, Twenty-Five Moves Suffice for Rubik’s Cube, Rokicki proves that there are no configurations that can be solved in exactly 26 moves. Taken with earlier results, this means that 25 movies should suffice for any solution.
“How many moves does it take to solve Rubik’s Cube? Positions are known that require 20 moves, and it has already been shown that there are no positions that require 27 or more moves; this is a surprisingly large gap. This paper describes a program that is able to find solutions of length 20 or less at a rate of more than 16 million positions a second. We use this program, along with some new ideas and incremental improvements in other techniques, to show that there is no position that requires 26 moves.”
KFC writes on the the physics arXiv blog that
“Rokicki’s proof is a neat piece of computer science. Heâ€™s used the symmetry of the cube to study transformations of the cube in sets, rather than as individual moves. This allows him to separate the â€œcube spaceâ€ into 2 billion sets each containing 20 billion elements. He then shows that a large number of these sets are essentially equivalent to other sets and so can be ignored. Even then, to crunch through the remaining sets, he needed a workstation with 8GB of memory and around 1500 hours of time on a Q6600 CPU running at 1.6GHz.”
Rokicki is working to establish a bound of 24 moves and thinks that a bound of 20 can eventually be proved.
March 17th, 2008
You drop a pen on the moon. Does the pen
a) float off into space,
b) float where it is, or
c) fall down?
Disturbingly, a majority answers either a or b. When asked, as a follow up, why astronauts don’t float when they’re on the moon, the majority answer is “because they have heavy boots.”
If you have a hard time believing this, I encourage you to start asking around. I asked some educated teenagers I know, and the first three of them answered either a or b.
“And why don’t astronauts float on the moon?”
I mention this because a theme of SciBarCamp was “10 Things Everyone Should Know About Science”. This was motivated by organizer Eva Amsen’s recently surveying a number of people about to receive PhDs, and finding that none of them knew what a gene is. She felt strongly that everyone should know that genes are segments of DNA that code for proteins, and started to wonder what else everyone should know. We all made suggestions on a large poster board at the Friday reception, and then had a panel and heated discussion on the subject Sunday morning. Eva has promised to post the results on her blog.
Strangely (and somewhat embarrassingly) there was not a single scientific fact on the list. Everything was about the process of science, the purpose of science, the practice of science, etc. In everyone’s defense, these are important topics that are fun to argue about. Passionate on the subject, I used my turn to speak about infant behavior as a model of inquiry. But, given the chance at a do-over, would anyone disagree that gravity deserves a spot in the top 10? In fact, shouldn’t it be number 1?
Technorati tags: SciBarCamp
March 17th, 2008
The blog is ours!
Now I can finally post about SciBarCamp, held last weekend in Toronto, and the most interesting meeting I’ve attended this millenium. Amongst its many highlights were two talks by Andrew Hessel. The first was about synthetic biology. Andrew helps run iGEM, which every year hands out “BioBricks” to high school and undergrad students around the world, and sees who can build the best genetic machines. Stunning successes have included a group of kids from Edinburgh who created a bacterium that changes the acidity of water, but only if there’s arsenic present. This enables individual wells to be tested at a cost of dimes instead of tens of dollars. (For a sickening account of why this is significant, click here, or here.) Another group invented a glowing bacterium which, I think, has a variety of computational and artistic applications.
The synthetic biology talk was part of a debate with Jim Thomas from etc, a group that monitors technology from a social justice perspective. Jim began by engendering sympathy for the Luddites, reminding us that in 1812, 14 Luddites were hanged near his alma mater in York, England. Before smashing things, Luddites would sometimes ask the people “is this harmful for the common good?”, and that’s the question Jim asked of synthetic biology. He didn’t exactly say yes, but he raised a number of concerns – security, safety, economic disruption, and concentration of corporate power. The only one which I really bought into was security; kids, as we know, do not use their creativity and hacking skills exclusively for good, and neither do adults. Part of Jim’s evidence was the case of Eckard Wimmer from Stony Brook, who built the polio virus from mail-order parts, just to show it could be done. The session ended before Andrew could respond.
Technorati tags: SciBarCamp