In the Media

MIT researchers used tools of computational complexity and mathematical concepts to prove that no analysis of the Super Mario Bros video game level “can say for sure whether or not it can ever be completed,” reports Matthew Sparkes for New Scientist. “The idea is that you’ll be able to solve this Mario level only if this particular computation will terminate, and we know that there’s no way to determine that, and so there’s no way to determine whether you can solve the level,” says Prof. Erik Demaine.