1.1.2 Cálculo lambda
El cálculo lambda es un modelo de computación que está basado en funciones computables. Fue creado por Alonzo Church y lo veremos con mayor detalle en la parte II del libro (capítulo 4), pero aquí daremos un esbozo general del modelo. Al igual que Alan Turing con su máquina de Turing, el cálculo lambda de Alonzo Church probó negativamente el problema de decisión.
A diferencia de la máquina de Turing, que tiene un proceso secuencial, el cálculo lambda construye la computación a través de funciones computables que se forjan en una notación formal con una gran expresividad. El cálculo lambda es una máquina de recursividad que cuenta con operadores, variables y operaciones de reducción (conocida como reducción b). Por tanto, hace un uso asiduo de la recursividad y de mantener estados inmutables en cada una de sus fases de reducción o derivación.
Antes de presentar una función lambda, es fundamental entender qué es una función matemática. Una función se puede definir de la siguiente manera: f:a → b, donde la función f recibe un valor a y devuelve b. Además, a y b pueden ser representados como conjuntos de elementos. Así, la función es una relación entre elementos de dos conjuntos.
Para nuestro ejemplo, el conjunto a se llama «dominio» y el conjunto b «codominio»; representan al conjunto de entrada y salida respectivamente. En notación conjuntista esta misma función puede ser definida de la siguiente manera: f(a) = b. Un ejemplo puede ser una función f que recibe un número entero que incrementa en 1. En este caso, f(x) = x + 1. Si a x se le asigna el valor 5, o sea, f(5) = 5 + 1, devolvería 6.
Entonces, volviendo a las funciones lambda, estas tienen como mecanismo de operación la reducción hasta donde sea posible. A esto lo llamamos computación.
Un ejemplo de función lambda es la siguiente:
(λx.(λy.y)x) (λy.y)
donde la función lambda es (λx.(λy.y)x) y el argumento es (λy.y). Para derivar o reducir esta función se puede aplicar reducción β, que es una propiedad del cálculo lambda:
(λx.(λy.y)x) (λy.y)
= (λy.y) (λy.y)
= (λy.y)
Termina las operaciones cuando alcanza la función (λy.y), que es, dicho sea de paso, una función de identidad que no puede ser reducida porque ya no tiene argumentos a la derecha. Para comprender esta reducción, vea la figura 1.5, donde se indica el argumento (desde donde nace la flecha, a la derecha), junto con la variable «X» (fase 1), y la variable «y» (fase 2) vendría a ser la posición donde dicho argumento tendrá su lugar (sustitución).
Básicamente, el primer paso es aplicar el primer argumento, (λy.y), a la función de la derecha. Y, debido a que toda variable que se encuentra a la derecha del símbolo λ se asocia a un argumento, esto quedaría así: [x:= (λy.y)]. Por lo tanto, se aplica una sustitución. (Una función lambda solo acepta un argumento.)
Así, a cada paso de reducción se aplica una sustitución de términos, hasta donde sea posible. Esto conlleva que la primera función exhibida se reduzca a la expresión (λy.y), donde ya no es posible continuar derivando.
Figura 1.5 Reducción de una función lambda, donde el primer argumento es (λy . y) y sustituye a la variable «X» definida dentro de la función lambda. Así, en la fase 2, se crea una reducción y vuelve a sustituir la siguiente variable, hasta llegar a la fase 3, donde ya no es posible aplicar ninguna otra reducción.
Podríamos decir que el cálculo lambda es un pequeño lenguaje de programación que permite expresar la computación a través de una sintaxis simple, acotada, flexible y, a su vez, poderosa. Algo para tener en cuenta es que una función lambda como (λ x.x) tiene una variable «X» que no especifica nada sobre el tipo de dato que tiene, es decir, este cálculo lambda es no tipado o libre de tipos, porque así fue presentado por Alonzo Church para la primera versión del cálculo lambda. La idea central, entonces, es ver que podemos manejar una función lambda como un valor y usarla como argumento de otra función lambda.
Esto último trae consigo alcances que explican las características de los lenguajes de programación funcionales y su surgimiento.
1.1.3 Otros
La máquina de Turing y el cálculo lambda no son los únicos modelos de computación. Existen muchos más e incluso hoy en día aparecen nuevos. Por otro lado, cada lenguaje de programación es, en sí mismo, un modelo de computación. Es por ello que se tiende a decir que un lenguaje como C++ o Python es «Turing completo», porque puede ser equivalente al funcionamiento de una máquina de Turing universal. Esto no acontece con otros lenguajes, como HTML o XML, que solo son de marcados y carecen de las características de un lenguaje de programación (condicionales, flujo de control, etc.).
Los modelos de computación, desde un punto de vista teórico de la computación, se pueden agrupar en tres categorías:
• Secuencial. En esta categoría caen los clásicos modelos de autómatas, finitos y con pila. Por otro lado, tenemos las máquinas de acceso aleatorio (RAM) y la máquina de Turing. Cada uno de ellos se cataloga como secuencial porque sigue un mecanismo paso a paso por cada operación.
• Funcional. El modelo de funciones recursivas, lógica combinatoria y, obviamente, el cálculo lambda. La idea principal no es la secuencia de paso, sino más bien construir la computación a través de funciones y reducción de estas.
• Concurrente. Algunos, como el autómata celular, la máquina paralela de acceso aleatorio (PRAM), el modelo en actores y la red de Petri, son modelos concurrentes. ¿Por qué concurrentes? Porque pueden suceder eventos que no siguen una secuencia y, en cambio, pueden «ejecutarse» fuera de un orden parcial sin afectar el resultado final de la computación.
1.2 TESIS DE CHURCH-TURING
Producto de la equivalencia entre los dos modelos, el cálculo lambda y la máquina de Turing, aparece el concepto de la tesis de Church-Turing, que reza lo siguiente:
Cualquiera que sea la función computable (algoritmo), esta es equivalente a una máquina de Turing.
Es decir, para que una función sea computable debe ser sí o sí computable por una máquina de Turing. En la actualidad, esto se sigue cumpliendo, y es difícil adherirse a la idea de que la tesis sea falsa, aunque es formalmente indemostrable. Esto radica en la incapacidad actual de definir qué es un «método efectivo» o «algoritmo», ya que no son conceptos fácilmente definibles. Simplemente se asume que cualquier algoritmo es una máquina de Turing.
Sobre esto, B. A. Trakhtenbrot, en su artículo: «Algorithms» de 1960, dijo lo siguiente sobre la incapacidad de demostrar esta tesis o hipótesis:
¿Cuál es la base de esta importante hipótesis? No podemos comprobarla como lo hacemos con un teorema matemático, puesto que es una declaración sobre el concepto general de algoritmo, que no está definido de manera precisa y no es, por tanto, un objeto propio de la discusión matemática. (Trakhtenbrot, 1960)
Sin embargo, en las últimas décadas se han añadido más datos que la han confirmado, por ejemplo, la equivalencia con otros modelos de