Page 36 - 06 Turing

Paso 5. Resolver la ecuación resultante en el paso anterior.

- Paso 6. Fin.

De estas consideraciones concluiremos que un ordenador es
una máquina de Turing universal que procesa algoritmos. Cuando

ALONZO CHURCH, EL CÁLCULO LAMBDA Y LISP

Pese a que la figura de Alan Turing ha
estado siempre ligada a la máquina que
lleva su nombre, lo cierto es que cuando
dio a conocer su trabajo otro matemático
de gran talla, Alonzo Church (1903-1995),
había publicado un trabajo con el que
restaba algo de originalidad al realizado
por Turing. Durante los años treinta,
Church introdujo, junto con Stephen
Kleene (1909-1994), el denominado cál-
culo 'A., una abstracción matemática con
la que estud iar qué es una función. Una
función es una expresión matemática
y= f(x) que relaciona el valor de dos va-
riables, por ejemplo la longitud x y el
peso y en las ballenas azules por medio
de la expresión y= 3,15 x-192. Aunque
este concepto fue introducido en el siglo
xv11 por Descartes, Newton y Leibniz, fue
de nuevo reconsiderado en los años treinta del siglo xx con el fin de elaborar
una teoría general sobre funciones matemáticas.

Una nueva sintaxis
Uno de los méritos de Church fue introducir una nueva sintaxis con la que re-
presentar a esta clase de expresiones matemáticas. Así, por ejemplo, si eva-
luamos la expresión (+(• 2 3)C-5 6)) -el asterisco es el operador multiplica-
ción- , entonces tendremos que el resultado es 36, ya que (2 · 3) + (5 · 6) =
= 6 + 30 = 36. Por consiguiente, una función matemática sería una abstracción.
De una forma similar, para el cálculo 'A., se usa una expresión algo más enre-
vesada, ('A.x. + x 1), que significaría lo que sigue: «La función (representada por

36 WUÉ ES UN ORDENADOR?