En 1936, Alan Turing en su trabajo "En números computables", introduce el concepto de la máquina de Turing y, junto a Alonzo Church demostraron ambos que es imposible escribir tal algoritmo.