-
David Hilbert
Formuló en 1928, durante el transcurso del congreso internacional: Si las Matemáticas son completas, consistentes y decidibles. -
David Hilbert
Tenía como objetivo crear un sistema matemático formal "completo" y "consistente". Por desgracia para Hilbert en la década de 1930 se produjeron una serie de investigaciones que demostraron que su teoría no era posible. -
K. Godel
Las primeras noticias en contra surgen en 1931 K. Godel y su teorema de la 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" -
Tesis de Church Turing
Una de las cuestiones más estudiadas en la Teoría de la Compatibilidad ha sido la posibilidad de construir programas que decidan si un determinado algoritmo posee o no una determinada propiedad.
¿Calculan los algoritmos A y B la misma función? (Problema de la equivalencia)
¿Para el algoritmo A para una de sus entradas? (Problema de la parada)
¿Para el algoritmo A para todas sus entradas? (Problema de la totalidad)
¿Para el algoritmo A la función f? (Problema de la verificación) -
Church, Kleene, Turing y Post
El siguiente paso importante lo constituye la aparición casi simultánea en 1936 de varias caracterizaciones independientes de la noción de la calculabilidad efectiva, en los trabajos de Church, Kleene, Turing y Post. los tres primeros mostraban problemas que eran efectivamente indecidibles; church y Turing probaron además que el Entscheidungsproblem era un problema indecidible. -
McCulloch y Pitts
Describían los cálculos lógicos inmersos en un dispositivo (neurona artificial) dicho dispositivo recibía impulsos eléctricos que fueron catalogados como 1 y 0, esta notación es utilizada es la base para el desarrollo de expresiones regulares en la descripción de conjuntos de cadenas de caracteres que producen una entrada o salida. -
J. Von Neumann
Introduce el término teoría de autómatas y dice sobre los trabajos de McCulloch-Pitts “el resultado más importante de McCulloch-Pitts, 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 tal red neuronal formal”. -
Shanon
El matemático norteamericano Shanon (que luego se haría famoso por su Teoría de la Información) vino a establecer las bases para la aplicación de la Lógica Matemática a los circuitos combinatorios y posteriormente Huffman en 1954 los amplio a circuitos secuenciales y utiliza conceptos como estado de un autómata y tabla de transición. -
Noam Chomsky
Propone en 1956 tres modelos para la descripción de lenguajes, que son la base de su futura jerarquía de los tipos de lenguajes (1959), que ayudo también en el desarrollo de los lenguajes de programación. -
Shanon
A lo largo de las décadas siguientes, las ideas de Shanon se desarrollaron considerablemente, dando lugar a la formalización de una Teoría de las maquinas Secuenciales y de los Autómatas Finitos (1956). -
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 era el mismo descrito con expresiones regulares desarrollados con los trabajos de McCulloch-Pitts.
