Con esta pregunta Alan Turing, el padre de las computadoras, comienza su artículo "Solvable and Unsolvable problems", publicado en la revista Science News 31, pp 7-23 (1954). Por ejemplo tomemos el puzzle del 15, el puzzle más famoso de Sam Loyd que data de 1878. Se trata del cuadrado con fichas móviles numeradas del 1 al 15 y una posición libre. El objetivo es llevar las fichas a una posición ordenada. ¿Independientemente de cuál sea la posición inicial de las fichas, siempre se las puede desplazar hacia la configuración solución? Para este caso sabemos la respuesta. Pero el hecho de interés es que no existe un método sistemático general para testear puzzles y saber si son solubles o no. Y no es que todavía nadie ha encontrado el test que puede aplicarse a todo puzzle (en ese caso no habría nada demasiado sorprendente en esta charla), sino que Turing mismo ha demostrado que dicho test nunca será encontrado, porque no puede existir.