Entcheidungsproblem
Páginas: 5 (1009 palabras)
Publicado: 6 de noviembre de 2012
Entscheidungsproblem (Gödel y Turing)
Entscheidungsproblem: ¿Existe un algoritmo que decida si una proposición cualquiera en la lógica de primer orden es universalmente válida o no? (en toda estructura donde los axiomas supuestos son válidos)
PROPOSICIÓN
El problema de DECISIÓN
ALGORITMO
SI
NO
EPIMENIDES
“Como Cretense, es justo decir que todos los Cretenses sonmentirosos”
EL REY DAVID
“TODO HOMBRE ES UN MENTIROSO” (Salmo 116:11) MENTIRA
VERDAD SÓLO EN EL LENGUAJE
Y EN MATEMÁTICA???
Gottfried Wilhelm von Leibniz (1646-1716) - Cálculo integral - Números binarios - Calculadoras mecánicas - Filosofía analítica - Ley de la continuidad - Ley de la homogeneidad Matemático Físico Filósofo Político Legalista Estudioso de la Ética Teólogo Historiador“Construir una máquina que manipule símbolos para determinar los valores de verdad de las proposiciones matemáticas”
DAVID HILBERT (1862-1943) “El más prominente matemático de finales del siglo XIX y principios del Siglo XX” En 1900 presentó los 23 problemas más importantes de la matemática El tercero fue el “Problema de Decisión” (Entscheidungsproblem)
“Nosotros debemos conocer y nosotros vamos aconocer”
El problema de Decisión se resuelve si uno conoce un procedimiento que le permita decidir la validez (o satasfacibilidad) de una expresión lógica dada, mediante un número finito de operaciones.
KURT GÖDEL (1906-1978) “El trabajo de Gödel en lógica es más que monumental” (Von Neumann) “Su gran trabajo (…) iluminó el rol de la limitación en el conocimiento humano” (RobertOppenheimer) Sus teoremas recibieron el reconocimiento como “la verdad matemática más importante del siglo” por la Universidad de Harvard.
“Solamente voy al Instituto (de Estudios Avanzados de Princeton) para tener el privilegio de conversar camino a casa con Gödel” (A. Einstein)
El Teorema de Incompletitud (Gödel 1930) prueba la existencia de sentencias verdaderas en matemática que no se puedenprobar ni refutar (indecidibles).
COMO??? - Tómense las sentencias, axiomas, proposiciones, demostraciones y teoremas - Asígnese un número natural a cada una (Números de Gödel) - Constrúyase una proposición sobre la “demostrabilidad” de un teorema - Tómese la negación de esta proposición - Diagonalícese con el número de Gödel de esta misma proposición (G.Cantor) - La proposición resultante es: “Soyla prueba de que esta proposición no es demostrable” De manera equivalente: “Esta proposición es falsa”
“, cuando precede a sí mismo entre comillas, no es demostrable”, cuando precede a sí mismo entre comillas, no es demostrable.
PERO, ESTAS PROPOSICIONES INDECIDIBLES REFUTAN EL PROBLEMA DE DECISIÓN????
NO, porque no muestran si existe o no un procedimiento
para mostrar o no la validezde una proposición.
QUÉ ES UN PROCEDIMIENTO??? QUÉ ES UN ALGORITMO??? (respuestas en los años 1930's)
ALONZO CHURCH (1903-1995) Prueba a partir del Cálculo Lambda (λ-Calculus) (1936)
“EL PROBLEMA DE DECISIÓN NO TIENE SOLUCIÓN” ALAN TURING (1935)
COMO???? USANDO LA MÁQUINA UNIVERSAL DE TURING PARA DEFINIR PROCEDIMIENTOS (ALGORITMOS) DESDE EL PUNTO DE VISTA MATEMÁTICO
Sensor delectura, grabación y borrado
Máquina con un número finito de estados
Símbolos en la cinta
Cinta movible
IMAGEN CONCRETA DE UNA MÁQUINA DE TURING
EL PROBLEMA DE “PARADA”: Dado un programa de computadora cualquiera, decidir si el programa termina de correr o si corre indefinidamente.
(RICE)
Si se resuelve negativamente el problema de parada, no existirá un procedimiento paradeterminar si una proposición es válida o no lo es, porque si tuviéramos este procedimiento, podemos aplicarlo al mismo problema de parada. COMO RESOLVER EL PROBLEMA DE PARADA??? - Tómense todos los procedimientos (o algoritmos) - Asígnese un número natural a cada uno (Números de Gödel) - Constrúyase un algoritmo sobre la “No parada” de un algoritmo cualquiera - Tómese la negación de este...
Entscheidungsproblem: ¿Existe un algoritmo que decida si una proposición cualquiera en la lógica de primer orden es universalmente válida o no? (en toda estructura donde los axiomas supuestos son válidos)
PROPOSICIÓN
El problema de DECISIÓN
ALGORITMO
SI
NO
EPIMENIDES
“Como Cretense, es justo decir que todos los Cretenses sonmentirosos”
EL REY DAVID
“TODO HOMBRE ES UN MENTIROSO” (Salmo 116:11) MENTIRA
VERDAD SÓLO EN EL LENGUAJE
Y EN MATEMÁTICA???
Gottfried Wilhelm von Leibniz (1646-1716) - Cálculo integral - Números binarios - Calculadoras mecánicas - Filosofía analítica - Ley de la continuidad - Ley de la homogeneidad Matemático Físico Filósofo Político Legalista Estudioso de la Ética Teólogo Historiador“Construir una máquina que manipule símbolos para determinar los valores de verdad de las proposiciones matemáticas”
DAVID HILBERT (1862-1943) “El más prominente matemático de finales del siglo XIX y principios del Siglo XX” En 1900 presentó los 23 problemas más importantes de la matemática El tercero fue el “Problema de Decisión” (Entscheidungsproblem)
“Nosotros debemos conocer y nosotros vamos aconocer”
El problema de Decisión se resuelve si uno conoce un procedimiento que le permita decidir la validez (o satasfacibilidad) de una expresión lógica dada, mediante un número finito de operaciones.
KURT GÖDEL (1906-1978) “El trabajo de Gödel en lógica es más que monumental” (Von Neumann) “Su gran trabajo (…) iluminó el rol de la limitación en el conocimiento humano” (RobertOppenheimer) Sus teoremas recibieron el reconocimiento como “la verdad matemática más importante del siglo” por la Universidad de Harvard.
“Solamente voy al Instituto (de Estudios Avanzados de Princeton) para tener el privilegio de conversar camino a casa con Gödel” (A. Einstein)
El Teorema de Incompletitud (Gödel 1930) prueba la existencia de sentencias verdaderas en matemática que no se puedenprobar ni refutar (indecidibles).
COMO??? - Tómense las sentencias, axiomas, proposiciones, demostraciones y teoremas - Asígnese un número natural a cada una (Números de Gödel) - Constrúyase una proposición sobre la “demostrabilidad” de un teorema - Tómese la negación de esta proposición - Diagonalícese con el número de Gödel de esta misma proposición (G.Cantor) - La proposición resultante es: “Soyla prueba de que esta proposición no es demostrable” De manera equivalente: “Esta proposición es falsa”
“, cuando precede a sí mismo entre comillas, no es demostrable”, cuando precede a sí mismo entre comillas, no es demostrable.
PERO, ESTAS PROPOSICIONES INDECIDIBLES REFUTAN EL PROBLEMA DE DECISIÓN????
NO, porque no muestran si existe o no un procedimiento
para mostrar o no la validezde una proposición.
QUÉ ES UN PROCEDIMIENTO??? QUÉ ES UN ALGORITMO??? (respuestas en los años 1930's)
ALONZO CHURCH (1903-1995) Prueba a partir del Cálculo Lambda (λ-Calculus) (1936)
“EL PROBLEMA DE DECISIÓN NO TIENE SOLUCIÓN” ALAN TURING (1935)
COMO???? USANDO LA MÁQUINA UNIVERSAL DE TURING PARA DEFINIR PROCEDIMIENTOS (ALGORITMOS) DESDE EL PUNTO DE VISTA MATEMÁTICO
Sensor delectura, grabación y borrado
Máquina con un número finito de estados
Símbolos en la cinta
Cinta movible
IMAGEN CONCRETA DE UNA MÁQUINA DE TURING
EL PROBLEMA DE “PARADA”: Dado un programa de computadora cualquiera, decidir si el programa termina de correr o si corre indefinidamente.
(RICE)
Si se resuelve negativamente el problema de parada, no existirá un procedimiento paradeterminar si una proposición es válida o no lo es, porque si tuviéramos este procedimiento, podemos aplicarlo al mismo problema de parada. COMO RESOLVER EL PROBLEMA DE PARADA??? - Tómense todos los procedimientos (o algoritmos) - Asígnese un número natural a cada uno (Números de Gödel) - Constrúyase un algoritmo sobre la “No parada” de un algoritmo cualquiera - Tómese la negación de este...
Leer documento completo
Regístrate para leer el documento completo.