Entscheidungsproblem

Carta Común · N.º 256211

En ciencias de la computación y matemáticas, el Entscheidungsproblem (en español: problema de decisión) fue el reto en lógica simbólica de encontrar un algoritmo general que decidiese si una fórmula del cálculo de primer orden es un teorema. En 1936, de manera independiente, Alonzo Church y Alan Turing demostraron ambos que es imposible escribir tal algoritmo. Como consecuencia, es también imposible decidir con un algoritmo si ciertas frases concretas de la aritmética son ciertas o falsas. La pregunta se remonta a Gottfried Leibniz, quien en el siglo XVII, después de construir exitosamente una máquina mecánica de cálculo, soñaba con construir una máquina que pudiera manipular símbolos para determinar si una frase en matemáticas es un teorema. Lo primero que sería necesario es un lenguaje formal claro y preciso, y mucho de su trabajo posterior se dirigió hacia ese objetivo. En 1928, David Hilbert y Wilhelm Ackermann propusieron la pregunta en su formulación anteriormente mencionada. Una…

Leer en Wikipedia