Page 41 - 06 Turing

blem en inglés o Entscheidungsproblem en alemán). El problema
consiste en predecir si cuando una máquina de Turing lea un sím-
bolo de la cinta continuará funcionando o por el contrario se de-
tendrá, «colgándose», de forma similar a como lo hacen los
ordenadores actuales. Por consiguiente, la pregunta que intentaba
resolver Turing no es otra que la posibilidad de que exista un pro-
cedimiento mecánico, en la actualidad un programa de ordenador,
con el que sea posible establecer si otro programa se detendrá
cuando reciba como entrada un cierto valor o input. Hoy en día,
con cualquier ordenador de usuario es fácil hacer algunos experi-
mentos sencillos sobre estas y otras cuestiones teóricas plan-
teadas por Turing. Si asumin1os una equivalencia entre la máquina
de Turing y un ordenador en el que ejecutemos un progran1a, el
problema consistirá en decidir si dicho programa detendrá su eje-
cución o por el contrario se ejecutará indefinidamente. Experi-
mentaremos estas dos situaciones con los siguientes programas
en lenguaje BASIC-256. Por ejemplo, el siguiente programa se de-
tendrá apenas se ejecute una vez:

print "Hola Turing!"

mientras que este otro programa se ejecutará, una y otra vez, sin
detenerse nunca:

r=true
while r
print "Hola Turing!"
end while

Sin embargo, el problema estudiado por Turing y sus contem-
poráneos no es tan sencillo como aquí lo presentamos, ya que no
se puede desarrollar un procedimiento general que sea capaz de
llegar a conclusión alguna sobre la ejecución o parada de un pro-
grama cualquiera. El reto consiste en escribir un programa que
pueda tomar una decisión sobre esta cuestión, una vez que recibe
como datos de entrada o input no unos números, por ejemplo el
PIN de una tarjeta de crédito, o palabras, por ejemplo un nombre

WUÉ ES UN ORDENADOR? 41