-
Lógica matemática
Friedrich Ludwig Gottlob Frege 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 -
Lógica matemática
Kurt Gödel (1906 – 1978) Articulo 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.” -
Lógica matemática
Bertrand Russell (1872-1970) Principia mathematica es un conjunto de tres libros con las bases de la matemática escritos por Bertrand Russell y Alfred North Whitehead publicados entre 1910 y 1913 -
Lógica matemática
Principia mathematica Alfred North Whitehead -
Computabilidad
Alan Mathison Turing (1912 – 1954)- Creador de la Maquina Turing
- Publica en 1936 el artículo Los números computables, con una aplicación al Entscheidungsproblem. Nacimiento de la Informática Teórica
- Participa en la ruptura del cifrado de la máquina Enigma
-
Computabilidad
Alonzo Church (1903 – 1995) Desarrolla el cálculo lambda, basado en funciones
recursivas. (Base de los lenguajes funcionales) En 1936 demuestra la existencia de problemas
indecidibles para el cálculo lambda. 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. -
Computabilidad
Stephen Kleene (1909 - 1994) Discípulo de A. Church. Estudia la teoría de
funciones recursivas. Desarrolla las expresiones regulares
Numerosos estudios en Teoría de Autómatas -
Teoría de autómatas
Claude Elwood Shannon (1916 – 2001)
- En 1938publica A Symbolic Analysis of Relay and
Switching Circuits. Aplicación de la lógica
matemática a los circuitos electrónicos. – En 1948 publica Una Teoría Matemática de la
Comunicación. Nacimiento de la Teoría de la
Información- En 1956 edita, junto a McCarthy, Automata Studies, sobre máquinas secuenciales y autómatas finitos.
-
Teoría de autómatas
Autómatas Finitos Deterministas D. A. Huffman -Fue uno de los pioneros en el campo del origami matemático
-circuitos de conmutación secuencial -
Lingüística
Noam Chomsky 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 Autómatas finitos y sus problemas de decisión,
IBM J. Investigación y Desarrollo -
Teoría de autómatas
Autómatas de Pila M.P. Schutzenberger
En idiomas sin contexto y pushdown
autómata, información y control -
Complejidad computacional
Stephen Arthur Cook En 1971 publica The Complexity of Theorem Proving
Procedures, donde define las clases de problemas P, NP, y
NP completos.
