Archive for May, 2012

Solving problems with games

This post is about mostly things that I don’t know, but which are very interesting.. The basic topic is threefold:

1) sometimes computers are not capable of doing things, and sometimes it’s things that humans instead can do. I’m not speaking about having feelings or eating, but rather things that computers should be able to do better than humans, namely doing simulations, solving complicated problems, etc. Examples follow below.

2) on the other hand, humans are less easy (or cheap) to convince to do tasks, than computers, more or less by definition of a computer.. they seem to prefer much more playing videogames, looking at Facebook, or downloading illegally music and books.

3) on the other hand (i.e. on the fist hand) one can make those other “unproductive” preferred activities a tiny bit useful for the community (or rather for some precise guys), by using wicked tricks. One can use the same wicked tricks actually also to make the humans more useful to themselves.


A) One example where computers were beaten by humans is in relation to Foldit, a game devised to simulate protein folding. The recreational aspect hides a deep scientific importance, since no efficient way to simulate the folding process of proteins efficiently is yet known, the computational power available being one side of the limitation, and the lack of an algorithm adapted to the problem being the other. However online gamers have an edge on the machines, as shown in this article in Nature.

B) Similar stuff with RNA instead of proteins is called EteRNA.

C) Another project of similar nature is also done to help people place transistors on microchips efficiently, and the game is called FunSAT.

D) If you are interested in the sequencing of human genome, you might also know that the genome contains not all the answers about humans as we liked them. In fact, it looks more like a huge (sequenced) mess than like a nice programming code. One method to get some hints is Multiple Sequence Alignment, and is the topic of this game called Phylo.

E) A more boring (too scientific -looking) one is EyeWire, where you help a program to detect neurons of the retina.

F) During other activities than gaming, like downloading illegally books, or also during legal pseudo-activities like Facebook, you are sometimes asked to “prove that you’re human” by decyphering a text, composed of two words: a so-called captcha. (click link for a picture)

In some Captchas (for example the ones called reCAPTCHA) one of the words looks much more like a real, typed word than the other, and that’s why because the website you are accessing does not know that word, and you are actually helping some company transcribing scanned books from paper to digital format. The true verification is done through the other “artificial-looking” word.

If you try to write a random thing instead of the “book-word” then they will still think you are a human, while doing errors in the other “computer-made-word” is not forgiven (the computer just knows that part o the information).  Here is the guy who got the idea. He also got many other nice ideas. And a blog.

I wanted to write more about other aspects of this, but I’ll leave that for another post.


Leave a comment

branched trees with few leaves

I just thought of the following question, I’ve no idea if it’s a well-known riddle, but it seems a nice story, and it should not prove too difficult to answer:

God is tired before the 6th day of creation so he actually gives you a task, while he goes to take a nap. Namely you have to build the Amazon forest.  (That’s because people in the 21st century are going to need to chop trees in huge quantity in order to make paper, so the plan is that you have to fill the whole South America with trees before midnight). You take an energy drink and prepare to do the job…

Basically the technique to do one of these trees is quite simple: you are given some sticks and you have to glue them at their ends, making a caricature tree, then you plant one of these in the ground, and magically a leaf is going to sprout at the free end of the sticks, while the rest is becoming a realistic wodden tree.

You notice that the sticks become quite nice trunk pieces, while you don’t like so much the way the leaves come out, they seem boring to you (and you immagine that after all 21st century people will look more for wood than for leaves, so you want to concentrate on making that part). So you end up doing trees with many sticks, but as little leaves as possible. The result is not very nice, because you end up gluing all the sticks in a row, and you get a long tree with just one leaf in the end. This makes you wonder what would happen if you start doing a lot of branchings. And here is the question:

If you impose yourself that no gluing is done involving only 2 stick ends (so that your tree has just branch points, possibly with more than 2 branches), what is the least number of leaves that you can get if you use 4 sticks? What about 15 sticks? Is there a formula valid in the case of an arbitrary number of sticks?

Epilogue: Lost in those dreams you fall asleep, leaving an Amazon forest with a total of about 7 trees for the posterity.. but God is forgiving, so he offers you a beer.

Leave a comment