PROBLEMAS INDECIBLES
Los problemas indecibles son aquellos problemas matemáticos o computacionales para los cuales no existe un algoritmo que pueda determinar la respuesta correcta en todos los casos posibles. En otras palabras, no hay un procedimiento mecánico que pueda resolverlos de manera general.
1. Concepto y Origen
El estudio de los problemas indecibles surge en el ámbito de la teoría de la computabilidad, especialmente con los trabajos de Alan Turing y Kurt Gödel en la primera mitad del siglo XX.
Gödel (1931) demostró con sus teoremas de incompletitud que en cualquier sistema formal suficientemente potente (como la aritmética de Peano), existen enunciados verdaderos que no pueden ser demostrados dentro del sistema.
Turing (1936) introdujo el concepto de máquina de Turing y probó la existencia de problemas indecibles al demostrar que no existe un algoritmo para resolver el problema de la parada (halting problem).
2. Ejemplos de Problemas Indecibles
a) El problema de la parada
Dado un programa y una entrada, determinar si el programa se detendrá en algún momento o se ejecutará indefinidamente. Turing demostró que no hay un algoritmo general que pueda responder esta pregunta para todas las posibles entradas y programas.
b) El problema de la correspondencia de Post
Dado un conjunto de pares de cadenas, determinar si hay una secuencia en la que al concatenar las primeras partes se obtiene la misma cadena que al concatenar las segundas partes. También es indecidible en su forma general.
c) La indecibilidad del Entscheidungsproblem
David Hilbert planteó la cuestión de si existía un procedimiento algorítmico para determinar la validez de cualquier enunciado lógico en una teoría formal. Turing y Alonzo Church demostraron que esto es imposible.
3. Implicaciones
La existencia de problemas indecibles tiene profundas implicaciones en la computación, las matemáticas y la filosofía:
Límites de la computación: No todo problema matemático o lógico puede resolverse con un algoritmo.
Seguridad informática: Muchas cuestiones en análisis de programas están relacionadas con problemas indecibles, lo que implica que no se pueden construir herramientas perfectas para detectar errores en el código.
Filosofía de las matemáticas: Plantea preguntas sobre la naturaleza del conocimiento matemático y la posibilidad de un sistema formal que contenga todas las verdades.
Aquí teneis mas información: https://es.khanacademy.org/computing/ap-computer-science-principles/algorithms-101/solving-hard-problems/a/undecidable-problems
¡ Que buen trabajo! Me parece genial el tema elegido, es muy intersante saber que hay problemas matemáticos que no son capaces de ser resueltos. Has hablado claramente y los temas estan bien explicados y elegidos. Me parece genial que hables de su origen y su concepto y yo consideraría un punto a favor el hecho que pongas ejemplos para que todos nosotros podamos entenderlo micho mejor.
ResponderEliminarAqui dejo un enlace muy interesante https://es.m.wikipedia.org/wiki/Problema_indecidible