Entscheidungsproblem para niños
El Entscheidungsproblem (que en español significa "problema de decisión") fue un gran desafío en las ciencias de la computación y las matemáticas. Se trataba de encontrar un algoritmo general. Este algoritmo debería poder decidir si una frase o "fórmula" del cálculo de primer orden era un teorema (es decir, una verdad que se puede demostrar).
En 1936, dos matemáticos muy importantes, Alonzo Church y Alan Turing, demostraron por separado que es imposible crear un algoritmo así. Esto significa que no hay una forma automática y general de saber si ciertas frases matemáticas son verdaderas o falsas.
Contenido
¿Qué es el Problema de Decisión?
El problema de decisión se refiere a la búsqueda de un método o conjunto de pasos (un algoritmo) que pueda resolver cualquier pregunta de un tipo específico. En este caso, la pregunta era: ¿Es esta fórmula lógica una verdad demostrable?
Un Sueño Antiguo: Leibniz y la Lógica
La idea de resolver problemas matemáticos con una máquina no es nueva. En el siglo XVII, el famoso pensador Gottfried Leibniz ya soñaba con esto. Después de crear una máquina que podía hacer cálculos, imaginó una máquina que pudiera manipular símbolos. Su objetivo era determinar si una frase matemática era un teorema. Para lograrlo, pensó que primero se necesitaría un lenguaje formal muy claro.
Mucho tiempo después, en 1928, los matemáticos David Hilbert y Wilhelm Ackermann plantearon la pregunta de forma más precisa. Querían saber si existía un algoritmo que pudiera decidir la validez de cualquier fórmula lógica.
¿Cómo se Define un Algoritmo?
Antes de poder responder al problema de decisión, era necesario definir qué es un "algoritmo" de manera formal. Esto lo lograron Alonzo Church y Alan Turing en 1936.
- Church usó su concepto de "calculabilidad efectiva", basado en algo llamado cálculo lambda.
- Turing, por su parte, lo hizo con su idea de la máquina de Turing.
Ambos enfoques son equivalentes. Esto significa que se pueden resolver exactamente los mismos problemas con cualquiera de las dos ideas.
La Respuesta Sorprendente: Es Imposible
La respuesta al Entscheidungsproblem fue negativa. Alonzo Church la dio en 1936, y Alan Turing, de forma independiente, la confirmó poco después, también en 1936.
Church demostró que no existe un algoritmo que pueda decidir si dos expresiones del cálculo lambda son iguales. Para esto, se basó en trabajos anteriores de Stephen Kleene.
Turing, por otro lado, relacionó este problema con el "problema de la parada" para las máquinas de Turing. El problema de la parada pregunta si se puede saber si un programa de computadora terminará de ejecutarse o si seguirá para siempre. Turing ya había demostrado que no hay un algoritmo general para resolver el problema de la parada.
Ambos trabajos fueron influenciados por las ideas de Kurt Gödel. Especialmente por su método de asignar números a las fórmulas lógicas. Esto permitía reducir problemas de lógica a problemas de aritmética.
El Argumento de Turing
El argumento de Turing se puede entender así: 1. Imagina que sí existe un algoritmo general para decidir si una fórmula lógica es verdadera. 2. Podríamos usar este algoritmo para traducir la pregunta sobre si una máquina de Turing se detiene. 3. Pero Turing ya había demostrado que no existe un algoritmo general que pueda decidir si una máquina de Turing se detiene. 4. Por lo tanto, el algoritmo general para la lógica de primer orden no puede existir.
¿Hay Casos Donde Sí se Puede Decidir?
Es importante saber que, aunque el problema general no tiene solución, sí hay casos específicos donde un algoritmo puede decidir. Si el problema se limita a una teoría de primer orden muy concreta, es posible que exista un algoritmo de decisión.
Algunos ejemplos de teorías donde sí se puede decidir son:
- La aritmética de Presburger, que es una parte de la aritmética.
- Los sistemas de tipos estáticos en los lenguajes de programación.
Sin embargo, la teoría general de los números naturales, conocida como la aritmética de Peano, no puede ser decidida con un algoritmo. Esto se debe al argumento de Turing que explicamos antes.
Véase también
En inglés: Entscheidungsproblem Facts for Kids
