-
En 1879Friedrich 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 -
– Problema de la decisión: descubrir un método general para
decidir si una fórmula lógica es verdadera o falsa -
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.” -
Definición de la Máquina de Turing como dispositivo matemático
abstracto de cálculo que introduce el concepto de “algoritmo”.
Origen “oficial” de la informática teórica.
Precursora abstracta de las máquinas de calcular automáticas.
La Máquina de Turing es un modelo abstracto de los ordenadores
actuales.
Demuestra la existencia de problemas irresolubles, los que
ninguna máquina de Turing (y ningún ordenador) puede resolver
o calcular. (Teoría de la Computabilidad). -
Aplicación de la lógica matemática a los circuitos
combinatorios y secuenciales -
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. -
Nacimiento de la Teoría de la Información
-
Chomsky clasificó de las gramáticas en diferentes tipos:
-Lenguajes del mismo tipo tienen propiedades en común
-Según el tipo de lenguaje, existen diferentes algoritmos que
permiten comprobar la sintaxis de textos.
