Automatas de hierro

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

  • Lógica matemática

    Lógica matemática
    Friedrich Ludwig Gottlob Frege
    - Publicó Conceptografía (Begriffsschrift)
    – Desarrollo de la lógica de primer orden (operadores and, or, not, implicación, para-todo, existe)
    – La notación que utilizaba era bastante complicada
  • El formulario

    El formulario
    Giuseppe Peano
    Propuso la notación actual de la lógica y estudió los principios de la matemática.
    FORMULARIO, enciclopedia con todas las fórmulas y teoremas conocidos en matemáticas
  • Principia Mathematica

    Principia Mathematica
    Bertrand Russell y Alfred North Whitehead
    Publicaron Principia Mathematica
  • David Hilbert

    David Hilbert
    Axiomatización de la geometría. Problemas de Hilbert.
    Publica en 1928 Principios de lógica teórica
    Problema de la decisión: descubrir un método general para decidir si una fórmula lógica es verdadera o falsa
  • Máquina de Turing

    Máquina de Turing
    En 1930´s, A. Turing desarrolló una máquina abstracta denominada Máquina de Turing para el estudio de la computabilidad.
  • Computabilidad

    Computabilidad
    Stephen Kleene
    Estudia la teoría de funciones recursivas.
    Desarrolla las expresiones regulares
    Numerosos estudios en Teoría de Autómatas
  • Teorema de incompletitud:

    Teorema de incompletitud:
    Kurt Göde
    “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

    Alonzo Church
    Desarrolla el cálculo lambda, basado en funciones
    recursivas. (Base de los lenguajes funcionales)
    - Publicó Conceptografía (Begriffsschrift)
    – Desarrollo de la lógica de primer orden (operadores and, or, not, implicación, para-todo, existe)
    – La notación que utilizaba era bastante complicada
  • Alan Mathison 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.
    Nacimiento de la Informática Teórica
  • Claude Elwood Shannon

    Claude Elwood Shannon
    Pública Aplicación de la lógica matemática a los circuitos electrónicos.
    Doctorado en 1955 en la U. Harvard con la tesis Estructura lógica de la teoría lingüística ( publicado en 1975)
    En 1957 publica Estructuras sintácticas en el que aparece la clasificación de gramáticas (Jerarquía de Chomsky)
  • Autómatas finitos

    Autómatas finitos
    En 1940´s y 1950´s, se desarrollan unas máquinas simples, en cuanto su funcionamiento, que fueron conocidas como autómatas finitos, para modelar el funcionamiento del cerebro.
  • McCulloch y Pitts

    McCulloch y Pitts
    Diseñan un dispositivo similar a 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.
  • Generadoras de lenguajes

    Generadoras de lenguajes
    1950´s, N. Chomsky comienza el estudio formal de las gramáticas (generadoras de lenguajes).
  • Lingüística

    Lingüística
    Noam Chomsky
    Doctorado en 1955 en la U. Harvard con la tesis Estructura lógica de la teoría lingüística (publicada en 1975)
    En 1957 publica Estructuras sintácticas en el que aparece la clasificación de gramáticas (Jerarquía de Chomsky)
  • Rabin y Scott

    Rabin y Scott
    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.
  • Complejidad Computacional

    Complejidad Computacional
    Stephen Arthur Cook
    Pública The Complexity of Theorem Proving Procedures, donde define las clases de problemas P, NP, y NP completos.
  • Norman E. Gibbs y Allen B. Tucker

    Norman E. Gibbs y Allen B. Tucker
    “No se debe 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 estructuras de datos, específicamente de sus propiedades formales”