Page 42 - 06 Turing

y los apellidos, sino otro programa. Concluiremos en este capítulo
que el problema de la parada es indecidible con una máquina de
Turing, pero ¿y con un ordenador?
Supóngase que llamamos parada (candidato, entrada)
a un programa que es capaz de establecer si otro programa, al que
llamaremos candi da to, detendrá o no su ejecución verificán-
dose su parada o halt cuando recibe un cierto valor de entrada o
input, cuyo valor denominaremos entrada. Efectivamente, si
representamos parada (candidato, entrada) en forma de
pseudocódigo, tendremos que:

programa parada(candidato, entrada)
if input=entrada y candidato - se detiene
then parada(candidato, entrada)=verdadero;
if input = entrada y candidato - no se detiene
then parada(candidato, entrada)=falso;

Supóngase que utilizando el programa parada ( candi da to,
entrada) escribiéramos un nuevo programa, al que denominare-
mos paradoja (entrada):

programa paradoja(entrada)
if parada(entrada, entrada)=falso
then return verdadero
else return falso

Demos un paso más en el razonamiento, tal y como hizo
Alan Turing, y llamemos P al progran1a paradoja. A continuación,
ejecutemos parada (P, P). Si el programa que está dentro del
principal devuelve falso, es decir, el programa P no se detiene
al recibir como valor de entrada o input un programa idéntico
a él, entonces el programa principal paradoja ( P) devolverá
verdadero, deteniéndose su ejecución, lo que no es cierto y por
tanto es «mentira».
Por el contrario, si parada ( P, P) devuelve verdadero,
puesto que el programa P detiene su ejecución al recibir un
valor similar de entrada P, entonces paradoja (P) no detiene

42 WUÉ ES UN ORDENADOR?