Problemas al diván ¿Todos los problemas son resolubles?
Dra. Laura Cecchi.
“En 1928, David Hilbert y Wilhelm Ackermann proponen el famoso Enstcheidungsproblem (problema de decisión, en alemán) «¿Existe un método efectivo, o algoritmo alguno, que permita determinar (dar respuesta tanto en caso afirmativo como negativo) si una sentencia cualquiera de la lógica de primer orden es tautología?»
Uno de los responsables de la respuesta a esta pregunta es el matemático inglés Alan Turing (1912-1954), quien se considera uno de los padres de la computación (particularmente de la teoría de la Computación y de la Inteligencia Artificial) ya que formalizó el concepto de Máquina de Turing y trajo con ella noticias desalentadoras sobre el Enstcheidungsproblem.
En esta matecharla describiremos qué es un problema de decisión, cómo se relaciona con los lenguajes formales, la importancia de los lenguajes formales en Ciencias de la Computación y qué es lo computable a partir de la noción de algoritmo y Máquina de Turing.
Hablaremos de la Jerarquía de Chomsky, relacionando lenguajes (regulares, libres de contexto, sensibles al contexto, recursivos y recursivos enumerables), gramáticas estructuradas por frases y autómatas.
Finalmente, nos detendremos a analizar problemas resolubles e irresolubles (Problema de la Parada) y sus consecuencias en las Ciencias de la Computación.
¡No son necesarios conocimientos de computación!
Se sugiere ver El código enigma (The Imitation Game), protagonizada por Benedict Cumberbatch como Turing o bien Breaking the Code, protagonizada por Derek Jacobi como Turing.
