Entscheidungsproblem y el inicio de la computación
Las computadoras desde mi punto de vista son el invento más importante del siglo XX, han cambiado radicalmente la manera en la que vivimos y especialmente nuestra manera de acercarnos a los problemas más complejos. Desde quienes se interesan por mejorar una campaña de marketing hasta quienes desean entender los jeroglíficos de una antigua civilización pasando por médicos, en todas las ramas del conocimiento y productivas se utilizan razonamientos computacionales para afrontar problemas gracias a la gran eficacia de este modo de pensar.
El inicio de las Ciencias de la Computación se puede señalar en el momento cuando tanto Alan Turing desarrolló las hoy llamadas máquinas de Turing como cuando Alonzo Church desarrolló la teoría del cálculo lambda, ambos modelos equivalentes de la computación abstracta. Uno de los primeros problemas que ambos resolvieron es el famoso entscheidungsproblem propuesto por David Hilbert más o menos en los años 30's.
En esta edición de nuestro bourbakisme hablaremos de lo siguiente:
- David Hilbert y la completitud de las matemáticas
- Alan Turing y Alonzo Church: dos formas de entender la computación
- ¿Qué dice el Entscheidungsproblem?
David Hilbert y la completitud de las matemáticas
En los años cercanos a 1900 había una creencia bastante generalizada entre los matemáticos sobre la posibilidad de demostrar cualquier teorema en matemáticas, tan fuerte eran estos puntos de vista que uno de los matemáticos más brillantes de toda la historia David Hilbert propuso una lista con los problemas que al resolverlos acabarían con el conocimiento matemático necesario. Hilbert hizo pública esta lista en París y desde entonces estas preguntas han guiado la búsqueda de los matemáticos en muchas áreas.
Afortunadamente (desde mi punto de vista) Hilbert estaba equivocado y las matemáticas pero especialmente el razonamiento lógico que nos permite demostrar un teorema matemático es mucho más complicado de lo que podemos imaginar. A pesar de que los primeros ejemplos de los problemas en la lógica se remontan a Russell, el primer gran avance de un matemático fue el teorema de incompletitud de Kurt Gödel quien demostró que en una teoría matemática aparentemente tan inocente como la aritmética de los números enteros (suma y multiplicación únicamente), es posible describir resultados que son ciertos aunque imposibles de demostrar matemáticamente utilizando la axiomatización de la aritmética. Este resultado cambiaría por completo nuestra manera de entender las matemáticas.
Alan Turing y Alonzo Church: dos formas de entender la computación
En la misma época apareció la figura mítica de Alan Turing, matemático y lógico británico, desarrolló el concepto de la máquina de Turing en 1936. La máquina de Turing es un modelo abstracto de una computadora que consiste en una cinta infinita, que actúa como una memoria, y un cabezal de lectura/escritura que puede moverse a lo largo de la cinta, leyendo y escribiendo símbolos según un conjunto de reglas predefinidas. Esta idea revolucionaria permitió a Turing formalizar lo que hoy conocemos como computación y proporcionó una base teórica para el desarrollo de las computadoras modernas.
A pesar de que la máquina de Turing es un concepto teórico, su importancia radica en que sentó las bases de la informática y la teoría de la computación, demostrando que existen problemas que no se pueden resolver mediante algoritmos. Su trabajo sentó las bases de la teoría de la computabilidad, que influiría enormemente en el desarrollo de las primeras computadoras electrónicas. Además, las máquinas de Turing continúan siendo fundamentales en la comprensión de los límites de lo que es computable, y su influencia se extiende hasta la informática teórica moderna.
Por el otro lado está Alonzo Church, un matemático y lógico estadounidense, desarrolló el cálculo lambda en la década de 1930 como una forma de formalizar la noción de función matemática y proveer una base para el estudio de los procesos computacionales. El cálculo lambda se centra en la manipulación de funciones mediante abstracciones y aplicaciones, utilizando una notación minimalista en la que las funciones se representan como expresiones que pueden ser aplicadas a argumentos. A diferencia de las máquinas de Turing, que operan con una cinta y reglas predefinidas, el cálculo lambda es un sistema de reglas simbólicas que formaliza cómo se pueden construir y aplicar funciones. Este enfoque se convirtió en un pilar fundamental de la teoría de la computación, pues permitió modelar computaciones sin depender de una máquina física, demostrando que los procesos algorítmicos pueden ser descritos de manera abstracta.
El cálculo lambda no solo fue esencial en el desarrollo de la teoría de la computación, sino que también tuvo un impacto profundo en la evolución de los lenguajes de programación. A través del cálculo lambda, Church introdujo la idea de la función anónima, que permite definir funciones sin necesidad de un nombre explícito, un concepto clave en muchos lenguajes de programación modernos. Además, el cálculo lambda sirvió como base para la teoría de los lenguajes funcionales, que se centran en el uso de funciones como elementos primarios de la programación. El trabajo de Church en el cálculo lambda, junto con las ideas de Turing, ayudó a sentar las bases para la informática moderna, mostrando que los procesos computacionales pueden ser descritos formalmente tanto a través de máquinas como mediante símbolos matemáticos abstractos.
¿Qué dice el Entscheidungsproblem?
El Entscheidungsproblem fue formulado por David Hilbert en 1928 como una pregunta central en la lógica matemática: ¿existe un algoritmo general que pueda determinar si una afirmación matemática es universalmente verdadera o falsa, es decir, decidir si una proposición es demostrable dentro de un sistema formal dado? Originalmente Hilbert lo planteó en general sobre cualquier afirmación que hace un ser humano sin embargo inclusive en el contexto de las matemáticas esto no es cierto.
Este problema surgió en el contexto de la búsqueda de un método sistemático para resolver todas las preguntas matemáticas mediante una secuencia finita de pasos. Sin embargo, tanto Alonzo Church como Alan Turing demostraron, de manera independiente, que este problema era irresoluble, lo que tenía profundas implicaciones para la lógica y la teoría de la computación.
La demostración de Church se basó en su desarrollo del cálculo lambda, una formalización de las funciones y sus aplicaciones. Church demostró que no existe un algoritmo general que resuelva el Entscheidungsproblem al demostrar que el cálculo lambda es Turing-equivalente: si se pudiera decidir cualquier afirmación dentro de este sistema, entonces también se podría decidir el comportamiento de cualquier función computacional.
Por otro lado, Turing abordó el problema desde una perspectiva diferente, desarrollando la máquina de Turing, un modelo abstracto de computación que también demostró que no existe un algoritmo universal para decidir todas las proposiciones en un sistema formal. Turing probó que el problema de la parada (el problema de determinar si un programa se detendría o no) es indecidible, lo que implica que el Entscheidungsproblem no tiene solución general. Ambas demostraciones, aunque basadas en diferentes enfoques, llegaron a la misma conclusión: la imposibilidad de un algoritmo general para la decisión en sistemas formales, un resultado que cambió el rumbo de la lógica y la computación.
¿Dónde aprender matemáticas y ciencias de la computación?
En el Colegio de Matemáticas Bourbaki enseñamos con detalle las matemáticas y las bases para que nuestros estudiantes estén listos para aprender los modelos más avanzados de Inteligencia Artificial, Ciencia de Datos y Finanzas Cuantitativas. Estos son los dos cursos que están por comenzar y durarán todo el 2025.
- Track de Ciencia de Datos. (49 semanas).
- Machine Learning & AI for the Working Analyst ( 12 semanas).
- Matemáticas para Ciencia de Datos ( 24 semanas).
- Especialización en Deep Learning. (12 semanas).
- Track de Finanzas Cuantitativas (49 semanas)
- Aplicaciones Financieras De Machine Learning E IA ( 12 semanas).
- Las matemáticas de los mercados financieros (24 semanas).
- Deep Learning for Finance (12 semanas).
