Page 37 - 06 Turing
P. 37
la solución a un problema es expresable por medio de un algoritmo,
se dice entonces que el problema es computable. El ingeniero suizo
Niklaus Wirth (n. 1934), autor de los lenguajes de programación
Algol, Modula-2 y Pascal, entre otros, introdujo en 1975 la definición
de un programa. De acuerdo con su definición, el programa es la
reunión del algoritmo con la forma de orgarúzar los datos dentro del
el símbolo A) de la variable (aquí x) -concepto que de una forma convencional
escribiríamos como"- (x)- que (representado como .) añade (por el operador
+) el valor de la variable (es decir, x) al». Podemos complicar un poco más la
expresión anterior, por ejemplo escribiendo ((Ax.+xl)3), cuyo resultado sería
4, porque estamos diciendo que el valor de x es 3. Como es previsible podemos
ir complicando las operaciones hasta desarrollar todos los elementos del cál-
culo "-· Otro de los méritos de esta clase de cálculo fue que tuvo un profundo
impacto sobre la teoría que estudia la programación de ordenadores.
El problema de la parada
Pero si por algo es célebre el cálculo "- es porque Church utilizó este forma-
lismo para estudiar el llamado problema de la parada, obteniendo como re-
sultado la noción de problema computable, que es precisamente la idea
que subyace en la máquina de Turing. A su vez, Turing demostró en 1937 que
tanto el cálculo "- como su máquina eran equivalentes, es decir, permitían
llegar por dos vías diferentes a los mismos resultados. Cuando una máquina
de Turing procesa alguna de las expresiones indicadas, por ejemplo (+31), se
detiene una vez obtenido un resultado, 4 en el ejemplo, siendo esta la expre-
sión computable. Más aún, y desde un punto de vista práctico, el cálculo "-
inspiró el desarrollo de los llamados lenguajes de programación funcionales,
uno de cuyos ejemplos es Lisp, uno de los lenguajes más importantes en in-
teligencia artificial. Este lenguaje fue introducido en 1958 por John McCarthy
(1927-2011), uno de los padres de la inteligencia artificial, y entre cuyas carac-
terísticas heredadas del cálculo "- se encuentra el uso de paréntesis:
(defstruct persona
(nombre ' Alan)
(edad 41))
o en el caso más sencillo:
(format t «¡Hola Turing 1 »)
WUÉ ES UN ORDENADOR? 37
