Historia y evolución de la teoría de autómatas y lenguajes formales

  • David Hilbert

    David Hilbert
    Fórmula las las cuestiones fundamentales:
    1.- ¿Son completas las matemáticas, en el sentido de que pueda probarse o no cada aseveración matemática? 2.- ¿Son las matemáticas consistentes, en el sentido de que no pueda probarse simultaneamente una aseveración y su negación? 3.- ¿Son las matemáticas decidibles, en el sentido de que exista un método definido que se pueda aplicar a cualquier aseveración matemática, y que determine si dicha aseveración es cierta?
  • Kurt Gödel. Teorema de la incompletitud

    Kurt Gödel. Teorema de la incompletitud
    Kurt Gödel publicó el “Teorema de la incompletitud”, donde demostraba que era imposible la completa axiomatización
    de las matemáticas.
  • Stephen Cole Kleene

    Stephen Cole Kleene
    Stephen Cole Kleene ideó la notación de las expresiones regulares, además de esto también demuestra la equivalencia entre funciones definibles y las funciones recursivas de Hembrand-Godel, dando ejemplos de problemas irresolubles utilizando la noción de función recursiva.
  • A. Church.

    A. Church.
    La suposición no demostrada de que cualquier forma general de computación no permite calcular sólo las funciones recursivas parciales (o, lo que es lo mismo, que las máquinas de Turing o las computadoras actuales pueden calcular) se conoce como hipótesis de Church.
  • Emil Leon Post

    Emil Leon Post
    Post formula un modelo de procedimiento efectivo a través de los llamado sistema deductivos normales.
  • Church, Kleene, Turing y Post

    Church, Kleene, Turing y Post
    Aparecieron varias propuestas que no empleaban máquinas con el fin de caracterizar lo que se puede calcular, entre las que se incluyen los trabajos de Church, Kleene y Post. Church, quienes mostraban problemas que eran efectivamente indecidibles. Church y Turing probaron además que el Entscheidungsproblem era un problema indecidible
  • Alan Turing. Máquina de Turing

    Alan Turing. Máquina de Turing
    El matemático inglés Alan Turing, público su artículo “Sobre los números computables”, presentando la Máquina de Turing, ratifica la teoría de Gödel, demostrando que muchos problemas perfectamente definidos no pueden ser resueltos mediante una M.T.
  • McCullon y Pitts

    McCullon y Pitts
    “A logical calculus of the ideas immanent in nervious activity”. Describen los cálculos lógicos inmersos en un dispositivo que habían diseñado para simular la actividad de una neurona biológica.
  • J. Von Neumann

    J. Von Neumann
    Sería J. Von Neumann quien introdujera el termino de teoría de autómatas, indica que el resultado mas importante de McCulloch-Pitts es que cualquier funcionamiento que pueda ser definido en todo, "lógicamente, estrictamente y sin ambigüedad", en un numero finito de palabras, puede ser realizado también por una red neuronal formal.
  • David A. Huffman

    David A. Huffman
    Define y utiliza conceptos relacionados con estado de un autómata y tabla de transiciones.
  • Shannon, C. E.

    Shannon, C. E.
    El matemático Shannon estableció las bases para la aplicación de la lógica matemática al diseño de los circuitos combinatorios y secuenciales. Las ideas de Shannon derivarían en la formalización de una teoría de máquinas secuenciales y autómatas, cuyo principal objetivo era representar de manera formal el comportamiento de un determinado dispositivo electrónico o mecánico.
  • J. W. Backus

    J. W. Backus
    Para el lenguaje Fortran y Naur, para el Algol, utilizaron una idea similar para describir dichos lenguajes de programación. Como resultado, en ocasiones se hace referencia a las GIC como las “gramáticas en forma de Backus-Naur”.
  • Michael Oser Rabin y Dana Scott

    Michael Oser Rabin y Dana Scott
    Obtienen un modelo de un computador con una cantidad finita de memoria, a esta la llamaron "autómata de estados finitos". De igual manera demostraron que su comportamiento, era básicamente el mismo que el descrito mediante expresiones regulares por McCulloch y Pitts.
  • N. Chomsky

    N. Chomsky
    N. Chomsky propuso las gramáticas independientes del contexto como un método de descripción de los lenguajes naturales y demostró que toda GIC podía expresarse de esta forma.