Foto

LINEA DE TIEMPO teoría de autómatas y lenguajes formales

  • D. Hilbert 1928

    D. Hilbert 1928
    El punto de partida son las cuestiones fundamentales que D. Hilbert formuló en 1928, durante el transcurso de un congreso internacional:
    1.- ¿Son completas las matemáticas?
    2.- ¿Son las matemáticas consistentes ?
    3.- ¿Son las matemáticas decidibles?.
    La meta de Hilbert era crear un sistema matemático formal completo y consistente". Su idea era encontrar un algoritmo que
    determinara la verdad o falsedad de cualquier proposición en el sistema formal.
  • Period: to

    Teoría de Autómatas y Lenguajes Formales

    El desarrollo de los ordenadores, con la introducción de los programas en la memoria principal, y posteriormente con los lenguajes de programación de alto nivel,propician la distinción entre lenguajes formales, con reglas sintácticas y semánticas rígidas, concretas y bien definidas, de los lenguajes naturales como el inglés, donde la sintaxis y la semántica no se pueden controlar fácilmente.
  • D. Hilbert 1930

    D. Hilbert 1930
    Por desgracia para Hilbert, en la década de 1930 se produjeron una serie de investigaciones que mostraron que no era posible sus teorías.
  • K. Gödel 1931

    K. Gödel 1931
    Teorema de Incompletitud: "Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de axiomas sea recursivo, no es completo."
    Un aspecto a destacar dentro del teorema de incompletitud de Gödel, fue la idea de codificación.
    A través del código, los enunciados referentes a enteros positivos, pueden considerarse como enunciados referentes a Números de código de expresiones, o incluso referentes a las propias expresiones.
  • Church 1936

    Church 1936
    Church propuso la función definible como función calculable. La demostración se convierte en una transformación de cadena de símbolos en otra,según un conjunto de reglas formales.Este sistema fue inconsistente,pero la capacidad para calcular funciones numéricas como términos del sistema llamó su atención.Hace un esquema de la demostración de la equivalencia entre las funciones definibles y las recursivas y aventura que iban a ser las únicas funciones calculables por medio de un algoritmo.
  • Kleene 1936

    Kleene 1936
    Por otra parte Kleene, pocos meses después, demuestra formalmente la equivalencia entre
    funciones λ-definible y funciones recursivas de Herbrand-Gödel, y da ejemplos de problemas irresolubles utilizando la noción de función recursiva.
  • A. Turing 1936

    A. Turing 1936
    La tercera noción de función calculable proviene de A Turing,quien
    señaló que había tenido éxito en caracterizar de un modo matemáticamente preciso, por medio de sus máquinas, la clase de las funciones calculables mediante un algoritmo, lo que
    se conoce hoy como Tesis de Turing. Aunque no se puede dar ninguna prueba formal de que una máquina pueda tener esa propiedad, Turing dió un elevado número de argumentos a su favor, en base a lo cual presentó la tesis como un teorema demostrado.
  • E. Post 1936

    E. Post 1936
    Finalmente, cabe reseñar el trabajo de E. Post. Este estaba interesado en marcar la frontera
    entre lo que se puede hacer en matemáticas simplemente por procedimientos formales y lo que
    depende de la comprensión y el entendimiento. De esta forma, Post formula un modelo de procedimiento
    efectivo a través de los llamados sistemas deductivos normales.
  • Kleene 1938

    Kleene 1938
    Los resultados hasta ahora citados, se refieren a funciones totales. La existencia de algoritmos
    que con determinadas entradas nunca terminan, condujo de forma natural a considerar
    funciones parciales. Kleene fué el primero en hacer tal consideración en 1938
  • McCulloch y Pitts 1943

    McCulloch y Pitts 1943
    Describen los cálculos lógicos inmersos en dispositivo que habían diseñado para simular la actividad de una neurona biológica. El dispositivo recibía o no, una serie de impulsos eléctricos por sus entradas que se ponderaban, y producía una salida binaria. Las entradas y salidas se podían considerar como cadenas de 0 y 1, indicando entonces la cadena de entrada para producir la salida. La notación es la base para el desarrollo de expresiones en descripción de conjuntos de cadenas de caracteres.
  • C. Shannon 1948

    C. Shannon 1948
    Define los fundamentos de la teoría de la información, y utiliza esquemas para poder definir sistemas discretos, parecidos a los autómatas finitos, relacionándolos con cadenas de Markov, para realizar aproximaciones a los lenguajes naturales.
  • J. Von Neumann 1948

    J. Von Neumann 1948
    Introduce teoría de autómatas, y dice sobre los trabajos de McCulloch-Pitts: “el resultado más importante de estos, es que cualquier funcionamiento en este sentido, que pueda ser definido en todo, lógicamente, estrictamente y sin ambigüedad, en un número finito de palabras, puede ser realizado también por una red neuronal formal”, La necesidad de traducir los algoritmos escritos en lenguajes de alto nivel al lenguaje máquina,propicia la utilización de máquinas como autómatas de estados finitos
  • Kleene 1951

    Kleene 1951
    Realiza un informe sobre los trabajos de McCulloch-Pitts, que se publica en 1956. En este informe, Kleene demuestra la
    equivalencia entre lo que él llama "dos formas de definir una misma cosa", que son los sucesos regulares (que se pueden describir a partir de sucesos bases y los operadores unión, concatenación
    e iteración (*) ), es decir, expresiones regulares, y sucesos especificados por un autómata finito
  • D. A. Huffman 1954

    D. A. Huffman 1954
    Ya utiliza conceptos como estado de un autómata y tabla de transiciones.
  • N. Chomsky 1956

    N. Chomsky 1956
    Propone tres modelos para la descripción de lenguajes, que son la base futura jerarquía de los tipos de lenguajes, que ayudó también en el desarrollo de los LP. Para ello intentó utilizar autómatas para extraer estructuras sintácticas y dirige sus estudios a las gramáticas, indicando que la diferencia esencial entre autómatas y gramáticas es que la lógica asociada a los autómatas es decidible, mientras que la asociada a las gramáticas no lo es.
  • C. Shannon y J. McCarthy 1956

    C. Shannon y J. McCarthy 1956
    En 1956, la Princenton Univ. Press publica el libro Automata Studies, editado por C. Shannon
    y J. McCarthy, donde se recogen una serie de trabajos sobre autómatas y lenguajes formales.
  • Rabin y Scott 1960

    Rabin y Scott 1960
    Obtienen un modelo de computador con una cantidad finita de memoria, al que llamaron autómata de estados finitos. Demostraron que su comportamiento posible, era básicamente el mismo que el descrito mediante expresiones regulares, desarrolladas a partir de
    los trabajos de McCulloch y Pitts.
  • Norman E. Gibbs y Allen B. Tucker 1986

     Norman E. Gibbs y Allen B. Tucker 1986
    indican que: ‘no debemos entender que el objetivo
    de las Ciencias de la Computación sea la construcción de programas sino el estudio sistemático
    de los algoritmos y estructura de datos, específicamente de sus propiedades formales’
  • A. Berztiss 1987

    A. Berztiss 1987
    Vamos a considerar a las C.C. como un cuerpo de conocimiento cuyo objetivo es obtener respuestas para las siguientes cuestiones:
    A) ¿Qué problemas se pueden resolver mediante un ordenador?.
    B) ¿Cómo puede construirse un programa para resolver un problema?.
    C) ¿Resuelve realmente nuestro programa el problema?.
    D) ¿Cuanto tiempo y espacio consume nuestro problema?.
    Analizando en profundidad los 4 puntos llegaremos a descubrir explícitamente los diferentes contenidos abarcados por las C.C.