Page 43 - 06 Turing

su ejecución, siendo también «mentira». Por consiguiente, Tu-
ring concluyó que dadas estas contradicciones el programa
parada, o halt en su versión original, carece de utilidad como
procedimiento que permita la evaluación de P. En otras pala-
bras, el problema de la parada o halting problem es un problema
irresoluble.
No obstante, y aunque no exista ningún programa que sirva
de herramienta universal para resolver satisfactoriamente el pro-
blema de la parada, sea cual sea el programa P, los científicos
pensaron que tal vez resultase factible escribir un programa que
devolviera únicamente respuestas a casos, es decir, en lenguaje
actual, programas particulares. Esta clase de programas fue bau-
tizada con el nombre de programas PHS (partial halting solver)
o solucionadores parciales de la parada. Sin embargo, tiempo
después se concluyó que la situación era tan intratable como el
problema de la parada. Por ejemplo, utilizando una vez más el
lenguaje BASIC-256, escribamos un programa que recibe como
entrada o input un programa P$. Su tarea consiste en proporcio-
nar como salida o output un comentario informando si el pro-
grama P$ detiene o no su ejecución:

input P$
if P$ = "halt" then
print "el programa SÍ se detiene"
else
print "el programa NO se detiene"
endif
end

De acuerdo con los razonamientos anteriores, la conclusión
a la que llegamos es realmente decepcionante, ya que no podemos
asegurar que este programa de apariencia tan sencilla propor-
cione al usuario únicamente respuestas correctas. Asombrosa-
mente, antes de que los ordenadores, y, por tanto, el software,
existieran, Turing fue capaz de llegar a la siguiente conclusión: no
existe ningún procedimiento mecánico, ya sea una máquina de
Turing o, en lenguaje actual, un programa de ordenador, con el

WUÉ ES UN ORDENADOR? 43