Des chercheurs du MIT ont découvert qu'aucun algorithme ne peut déterminer à l'avance si un niveau de Super Mario Bros est terminable, même pour les plus puissants superordinateurs. Cette impossibilité s'applique notamment à New Super Mario Bros et Super Mario Maker.

L'équipe a utilisé une "machine à compteur", équivalente à une machine de Turing, pour conclure qu'il faut jouer aux niveaux pour en vérifier la faisabilité. Ce phénomène pourrait expliquer pourquoi le jeu est considéré amusant et difficile.