Evolución de la Teoría de Autómatas y Lenguajes Formales - Jesús Matos (19-0260)
-
Friedrich Ludwig Gottlob Frege
Publicó Conceptografía (Begriffsschrift), desarrolló la lógica en primer orden (operadores and, or, not, implicación, para todo, existe, etc.). -
Giuseppe Peano
Propuso la notación actual de la lógica y estudió los principios de la matemática. Además formuló una enciclopedia con todas las fórmulas y teoremas matemáticos conocidos hasta la fecha. -
Bertrand Russell y Alfred North Whitehead
Publicación Principia Mathematica. -
David Hilbert
Axiomatización de la Geometría, planteó problemas a solucionar que más tarde sería denominados como los Problemas de Hillbert.
Publica en 1928 los Principios de la Lógica Teórica.
Plantea el problema de la decisión, que consistía en decidir si una fórmula lógica es verdadera o falsa. -
Kurt Godel
Logra demostra el Teorema de Incompletitud, que plantea:
"En cualquier formalización consistente de las matemáticas que sea lo bastante fuerte para definir el concepto de números naturales, se puede construir una afirmación que ni se puede demostrar ni se puede refutar dentro de ese sistema.” -
Alonzo Church
Desarrolla el cálculo lambda, basado en funciones recursivas. (Base de los lenguajes funcionales).
Demuestra la existencia de problemas indecidibles para el cálculo lambda.
Tesis de Church-Turing: plantea que cualquier modelo computacional existente tiene las mismas capacidades algorítmicas, o un subconjunto, de las que tiene una máquina de Turing. -
Alan Mathison Turing
Participa en la ruptura del cifrado de la máquina Enigma.
Publica el artículo Los números computables, con una aplicación al Entscheidungsproblem.
Fue crucial para el nacimiento de la Informática Teórica.
Inventa las máquinas de Turing.
