-
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 -
Lógica Matemática
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 -
Lógica Matemática
Bertrand Russell y Alfred North Whitehead
Publicaron Principia Mathematica -
Lógica Matemática
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 -
Computabilidad
Stephen Kleene
Estudia la teoría de funciones recursivas.
Desarrolla las expresiones regulares
Numerosos estudios en Teoría de Autómatas
Desarrolla el cálculo lambda, basado en funciones
recursivas. (Base de los lenguajes funcionales)
Demuestra la existencia de problemas
indecidibles para el cálculo lambda. -
Lógica Matemática
Kurt Göde
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.” -
Computabilidad
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
Inventa las máquinas de Turing -
Computabilidad
Alonzo Church
Desarrolla el cálculo lambda, basado en funciones
recursivas. (Base de los lenguajes funcionales)
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. -
Teoria de automatas
Claude Elwood Shannon
Pública 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. -
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 (que no se publicó hasta 1975)
En 1957 publica Estructuras sintácticas en el que aparece la clasificación de gramáticas (Jerarquía de Chomsky) -
complejidad computacional
Stephen Arthur Cook
Pública The Complexity of Theorem Proving Procedures, donde define las clases de problemas P, NP, y NP completos.
