Camilo Chacón Sartori - Computación y programación funcional

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.

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.

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 computación (por ejemplo, lenguajes de programación), los cuales se suelen llamar «Turing completo».

Las implicaciones de la tesis no son solo técnicas o científicas. También trae consigo cuestiones filosóficas. Si llevamos el concepto de máquina de Turing al mundo físico, por ejemplo, se podría postular que el universo es una máquina de Turing universal, donde, dada la tabla de instrucción (leyes físicas), podemos crear una simulación de nuestro universo. Aunque claro, una objeción sería que las leyes físicas no son computables (aunque eso no está probado), pero incluso si lo asumimos, nada nos asegura que no se pueda construir otra máquina incluso más poderosa que la máquina de Turing.

Siguiendo este mismo razonamiento, Jack Copeland creó el concepto de «hipercomputación» ( hypercomputation en inglés), el cual trata sobre la idea de poseer una máquina que no tenga los límites de una máquina de Turing. Con ello, se resolvería el problema de decisión. Aunque claro, la hipercomputación solo existe a nivel hipotético. Aun así, no se ha demostrado su imposibilidad.