|Ned Batchelder : Blog | Code | Text | Site|
» Home : Blog : March 2002
An interesting twist for fans of cellular automata: Minesweeper as the basis for computation. Richard Kaye has studied Minesweeper as a foundation for building logic components and Turing machines, and has therefore made connections between it and the theory of algorithms. I don't fully understand all the P and NP stuff, and there's clearly nothing practical about it, but there's something about this that tickles my geek funnybone.
I found this through the Clay Mathematics Institute, which has a more approachable description of the work as part of their prize problems: They're offering million-dollar prizes for solving hard classic math problems. Sharpen your pencils!