Alan Turing, en su famoso artículo «On computable numbers, with an application to the "Entscheidungsproblem"» (1936), demostró que el problema de la parada de la máquina de Turing es indecidible, en el sentido de que ninguna máquina de Turing lo puede resolver.