-
D. Hilbert (área del conocimiento matemática)
formuló las cuestiones fundamentales, durante el transcurso de un congreso internacional: -
K. Göde
Teorema de Incompletitud: (área del conocimiento matemática)
"Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de (números de Gödel de) axiomas sea recursivo no es completo." -
Church (área del conocimiento matemática)
Esquema de la demostración de la equivalencia entre las funciones γ-definibles y las funciones recursivas de Herbrand-Gödel, utilizando la noción de función γ-definible, dio ejemplos de problemas de decisión irresolubles, y demostró que el Entscheidungsproblem era uno de esos problemas. -
Kleene, (área del conocimiento matemática)
Demuestra formalmente la equivalencia entre funciones γ-definible y funciones recursivas de Herbrand-Gödel, y dá ejemplos de problemas irresolubles utilizando la noción de función recursiva. -
A. Turing, (área del conocimiento matemática)
Argumentó que la tercera cuestión de Hilbert (el Entscheidungsproblem) podía atacarse con la ayuda de una máquina, al menos con el concepto abstracto de máquina. Caracterizo 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. -
E. Post. (área del conocimiento matemática)
Formula un modelo de procedimiento efectivo a través de los llamados sistemas deductivos normales. Estos son sistemas puramente formales en los que puede ‘deducirse’ sucesiones finitas de símbolos como consecuencia de otras sucesiones finitas de símbolos por medio de un tipo normalizado de reglas y a partir de un conjunto de axiomas. Así pues, dada una sucesión finita de símbolos como entrada, las reglas permiten convertirla en una sucesión finita de salida. -
Kleene (área del conocimiento matemática)
La existencia de algoritmos que con determinadas entradas nunca terminan, condujo de forma natural a considerar funciones parciales -
McCulloch y Pitts (área del conocimiento matemática)
Describen los cálculos lógicos inmersos en un dispositivo (neurona artificial) 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 (existe pulso eléctrico o no). Las entradas y salidas se podían considerar como cadenas de 0 y 1, indicando entonces la forma de combinar la cadena de entrada para producir la salida. -
David Hilbert (área del conocimiento matemática)
"Todo problema matemático bien definido debe ser necesariamente susceptible de un planteamiento exacto, ya sea en forma de una respuesta real a la pregunta planteada o debido a la constatación de la imposibilidad de resolverlo, a lo que se debería el necesario fallo de todos los intentos... " -
C. Shannon (área del conocimiento informática)
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 (área del conocimiento informática)
Introduce el término de teoría de autómatas, La necesidad de traducir los algorítmos escritos en lenguajes de alto nivel al lenguaje máquina, propicia la utilización de máquinas como los autómatas de estados finitos, para reconocer si una cadena determinada pertenece (es una frase de) a un lenguaje concreto -
S.C. Kleene, (área del conocimiento informática)
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 -
John Backus
Director de proyecto de investigación en IBM para la realización de un lenguaje de programación más cercano a la notación matemática normal. Surgió el lenguaje FORTRAN, el primero de los lenguajes de programación de alto nivel que tuvo un gran impacto, incluso comercial, en la emergente comunidad informática.
Propuso una notación Backus-Naur(Backus-Naur Form o BNF) -
N. Chomsky
Propone tres modelos para la descripción de lenguajes, que son la base de su futura jerarquía de los tipos de lenguajes, que ayudó también en el desarrollo de los lenguajes de programación. -
Backus y Naur
Desarrollaron una notación formal para describir la sintáxis de algunos lenguajes de programación, que básicamente se sigue utilizando todavía, y que podía considerarse equivalente a las gramáticas libres del contexto. -
Rabin y Scott (área del conocimiento informática y computación)
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 -
. Hartmanis and R.E. Stearns, (área del conocimiento matemática)
Introducen la noción fundamental de medida de complejidad definida como el tiempo de computación sobre una máquina de Turing multicinta.