Monday, November 17, 2008

My Favorite XKCD Strips

This strip was about the limitations of complexity analysis. If something is unsolvable like TSP, it just means it is unsolvable on a Turing machine. There are other paradigms to try.

Here is another:

This is not technically impossible. It is about a cellular automata called Rule 34 which has been shown to be Turing Complete. i.e. it can simulate everything a gerneral purpose computer can do.