-
Friedrich Ludwig Gottlob Frege
En 1879 publicó Conceptografía (Begriffsschrift)
– Desarrollo de la lógica de primer orden -
Bertrand Russell (1872-1970)
Publica Principia Mathematica en 1910, 1912,
1913. -
David Hilbert (1862 – 1943)
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 -
Kurt Gödel (1906 – 1978)
Publica en 1931 el artículo Sobre proposiciones
formalmente indecidibles de Principia Mathematica y
sistemas relacionados
– Teorema de incompletitud:
“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.” -
Alan Mathison Turing (1912 – 1954)
Publica en 1936 el artículo Los números computables, con
una aplicación al Entscheidungsproblem. Nacimiento de
la Informática Teórica
– Inventa las máquinas de Turing -
Alonzo Church (1903 – 1995)
En 1936 demuestra la existencia de problemas
indecidibles para el cálculo lambda.
– Entre 1938 y 1939 trabaja con A. Turing
– Tesis de Church-Turing: cualquier modelo computacional
existente tiene las mismas capacidades algorítmicas, o un
subconjunto, de las que tiene una máquina de Turing. -
Claude Elwood Shannon (1916 – 2001)
En 1938 publica A Symbolic Analysis of Relay and
Switching Circuits. Aplicación de la lógica
matemática a los circuitos electrónicos. -
Claude Elwood Shannon (1916 – 2001)
En 1948 publica Una Teoría Matemática de la
Comunicación. Nacimiento de la Teoría de la
Información -
Claude Elwood Shannon (1916 – 2001)
En 1956 edita, junto a McCarthy, Automata Studies,
sobre máquinas secuenciales y autómatas finitos. -
Autómatas Finitos Deterministas
D. A. Huffman, The synthesis of sequential switching circuits, J.
Franklin Inst., vol. 257, (1954)
– G. H. Mealy, A method for synthesizing sequential circuits, Bell
System Technical Journal vol. 34 (1955)
– E.F. Moore, Gedanken experiments on sequential machines, en
Automata Studies (1956) -
Noam Chomsky (1928 - )
En 1957 publica Estructuras sintácticas en el que aparece la
clasificación de gramáticas (Jerarquía de Chomsky) -
Autómatas Finitos No Deterministas
M.O. Rabin y D. Scott, Finite automata and their decision problems,
IBM J. Research and Development, vol. 3 (1959) -
Autómatas de Pila
A. G. Oettinger, Automatic syntactic analysis and the pushdown
store, Proc. Symposia on Applied Math. (1961). -
Autómatas de Pila
M.P. Schutzenberger, On context-free languages and pushdown
automata, Information and Control
– P.C. Fisher, On computability by certain classes of restricted Turing
machines, Proc. 4th Annl. Symposium on Switching Circuit
Theory and Logical Design (1963) -
Stephen Arthur Cook (1939 - )
En 1971 publica The Complexity of Theorem Proving
Procedures, donde define las clases de problemas P, NP, y
NP completos.
