Teoría de Autómatas y Lenguajes Formales

Timeline created by jcamilo1022
  • Lógica Matemática - Friedrich Ludwig Gottlob Frege

    Lógica Matemática - Friedrich Ludwig Gottlob Frege
    Frege ideó un programa logicista destinado a explorar los fundamentos lógicos y filosóficos de las matemáticas y del lenguaje natura. Las dos obras fundamentales de Frege son su Begriffsschrift (1879, habitualmente traducido como Ideografía), que sentó las bases de la lógica moderna, y su Grundlagen der Arithmetik (1884, Fundamentos de la Aritmética), donde estableció los fundamentos filosóficos de las matemáticas
  • Lógica Matemática - Giuseppe Peano

    Lógica Matemática - Giuseppe Peano
    Publicó la quinta y última edición del Proyecto Formulario, titulado Formulario Mathematico. Contenía 4200 fórmulas y teoremas, todos completamente enunciados y la mayoría probados. Fue matemático, lógico y filósofo italiano, conocido por sus contribuciones a la lógica matemática y la teoría de números
  • Lógica Matemática - Principia Mathematica

    Lógica Matemática - Principia Mathematica
    Es un conjunto de tres libros con las bases de la matemática escritos por Bertrand Russell y Alfred North Whitehead publicados entre 1910 y 1913. Los Principia contenían teoría de conjuntos, números cardinales, números ordinales y números reales.
  • Lógica Matemática - David Hilbert

    Lógica Matemática - David Hilbert
    Axiomatización de la geometría, el texto Grundlagen der Geometrie (Fundamentos de la geometría), sustituye los tradicionales axiomas de Euclides por sistema formal de 21 axiomas. Propuso una lista muy influyente de 23 problemas sin resolver en el Congreso Internacional de Matemáticos de París. Se reconoce que esta es la recopilación de problemas abiertos más exitosa y de profunda consideración producida nunca por un único matemático. Publica en 1928 principios de la lógica teórica
  • Computabilidad - Stephen Kleene

    Computabilidad - Stephen Kleene
    Fundó la teoría de las funciones recursivas, un área de interés que sería investigada por él durante toda su vida. Lógico y matemático estadounidense. Introdujo la operación Clausura de Kleene, denotada por el símbolo V*, Es muy usada en expresiones regulares y fue introducida en este contexto para caracterizar un cierto autómata
  • Lógica Matemática - Kurt Gödel

    Lógica Matemática - Kurt Gödel
    conocido por sus dos teoremas de la incompletitud, el más célebre establece que para todo sistema axiomático recursivo auto-consistente lo suficientemente poderoso como para describir la aritmética de los números naturales, existen proposiciones verdaderas sobre los naturales que no pueden demostrarse a partir de los axiomas. Realizó contribuciones a la teoría de la demostración al esclarecer las conexiones entre la lógica clásica, la lógica intuicionista y la lógica modal.
  • Computabilidad - Alonzo Church

    Computabilidad - Alonzo Church
    Desarrolló el cálculo lambda, su trabajo que muestra la existencia de problemas indecidibles. Junto a Alan Turing trabajaron el problema de parada que también demostró la existencia de problemas irresolubles por dispositivos mecánico. Luego de revisar la tesis doctoral de Turing, demostraron que el cálculo lambda y la máquina de Turing utilizada para expresar el problema de parada tenían igual poder de expresión.
    Postuló la Tesis de Church-Turing
  • Comptabilidad - Alan Mathison Turing

    Comptabilidad - Alan Mathison Turing
    Participa en la ruptura del cifrado de la máquina enigma,
    considerado uno de los padres de la ciencia de la computación y precursor de la informática moderna, Proporcionó una influyente formalización de los conceptos de algoritmo y computación
    Formuló su propia versión que hoy es ampliamente aceptada como la tesis de Church-Turing.
    En su estudio Los números computables, con una aplicación al Entscheidungsproblem Turing reformuló los resultados obtenidos por Kurt Gödel
  • Teória de Autómatas - Claude Elwood Shannon

    Teória de Autómatas - Claude Elwood Shannon
    En su tesis doctoral en el MIT4​ demostró cómo el álgebra booleana se podía utilizar en el análisis y la síntesis de la conmutación y de los circuitos digitales. La tesis despertó interés cuando apareció en 1938 en las publicaciones especializadas, lo más notable fue lo referente a la teoría de la información, publicada en 1948 con el nombre de Una teoría matemática de la comunicación. Publicó en 1949 un trabajo que describía la programación de una computadora para jugar al ajedrez
  • Llenguajes y gramáticas - Avram Noam Chomsky

    Llenguajes y gramáticas - Avram Noam Chomsky
    Destacado gracias a sus trabajos en teoría lingüística y ciencia cognitiva, propuso la gramática generativa, disciplina que situó la sintaxis en el centro de la investigación lingüística. Cambió la perspectiva, los programas y métodos de investigación en el estudio del lenguaje. Su lingüística es una teoría de la adquisición individual del lenguaje explica la estructura y principios del lenguaje. Revolucionó la lingüística teórica con la publicación de la obra Estructuras sintácticas
  • Computabilidad - Stephen Arthur Cook

    Computabilidad - Stephen Arthur Cook
    Formalizó el concepto de NP-completitud en un famoso artículo de 1971 titulado "The Complexity of Theorem Proving Procedures" ("La complejidad de los procedimientos de demostración de teoremas"), donde también formuló el problema de la relación entre las clases de complejidad P y NP.
    La exploración de los límites de la clase de complejidad NP-completo ha sido una de las actividades investigadoras más activas e importantes en las ciencias de la computación durante la última década.