-
David Hilbert
Queria crear un sistema matemático formal completo,
consistente", en el que todas las aseveraciones pudieran plantearse con precisión. Pretendía encontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal. A este problema le llamó el ‘Entscheidungs problem’. -
Period: to
Teoría de la computabilidad
Posibilidad de construir algoritmos que nos determinen si un determinado algoritmo posee o no una determinada propiedad para responder de forma automática: Problema de la equivalencia, Problema de la parada, Problema de la totalidad, Problema de la verificación, etc. -
Period: to
Algoritmos para la solución.
(a) máquinas computadoras abstractas (definidas de modo preciso): son los Autómatas y las máquinas de Turing
(b) construcciones formales de procedimientos de cómputo: son los sistemas de Thue
(c) construcciones formales productoras de clases de funciones: las funciones recursivas -
K. Gödel
-Teorema de Incompletitud: "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."
-‘Las funciones recursivas de
Herbrand-Gödel’. -
Church y Turing
Probaron que el Entscheidungsproblem era un problema indecidible. -
Church
Hace un esquema de la demostración de la equivalencia entre
las funciones γ-definibles y las funciones recursivas de Herbrand-Gödel. -
Kleene
Demuestra 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
-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. -
E. Post.
Interesado en marcar la frontera entre lo que se puede hacer en matemáticas simplemente por procedimientos formales y lo que depende de la comprensión y el entendimiento -
Tesis de Turing.
Turing señaló que había tenido éxito en caracterizar de un modo
matemáticamente preciso, por medio de sus máquinas, la clase de las funciones calculables mediante un algoritmo -
Concepto de Máquina
Turing dió un elevado número de argumentos a su favor, en base a
lo cual presentó la tesis como un teorema demostrado. Además, utilizó su concepto de máquina para demostrar que existen funciones que no son calculables por un método definido y en particular, que el Entscheidungsproblem era uno de esos problemas -
Kleene
La existencia de algoritmos que con determinadas entradas nunca terminan, condujo de forma natural a considerar funciones parciales; esencial para el posterior desarrollo de la materia. -
Tesis de Church-Turing
Axioma en la teoría de la computación, y ha servido como punto de partida en la investigación de los problemas que se pueden resolver mediante un algoritmo. -
Máquina de propósito general. Codificación de Gödel
Capaz de resolver cualquier problema que
se pudiese resolver mediante un algoritmo. Dicha máquina tendría como entrada el entero que codificaría el algoritmo solución del problema y la propia entrada del problema, de tal forma, que la máquina aplicaría el algoritmo codificado a la entrada del problema. Considerada como el padre de las máquinas actuales. -
Period: to
AUTOMATAS Y LENGUAJES
Desarrollo de los ordenadores, introducción de
los programas en la memoria principal y los lenguajes de
programación de alto nivel -
McCulloch y Pitts
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 -
C. Shannon
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 -
J. Von Neumann
Introduce el término de teoría de autómatas, y dice sobre
los trabajos de McCulloch-Pitts: ... el resultado más importante de McCulloch-Pitts, es que cualquier funcionamiento en este sentido, que pueda ser definido en todo, lógicamente, estríctamente y sin ambiguedad, en un número finito de palabras, puede ser realizado también por una tal red neuronal formal. -
S.C. 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) -
D. A. Huffman
Utiliza conceptos como estado de un autómata y tabla de
transiciones. -
Princenton Univ. Press
Publica el libro Automata Studies, editado por C. Shannon y J. McCarthy, donde se recogen una serie de trabajos sobre autómatas y lenguajes formales. -
Jerarquía de Chomsky. N. Lenguajes formales
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 sintaxis 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. -
Complejidad Algorítmica. Rabin y Scott
Trata de estudiar la relativa dificultad computacional de
las funciones computables. Obtienen un modelo de computador con una cantidad finita de memoria, al que llamaron autómata de estados finitos -
Autómatas, computabilidad, e incluso la complejidad algorítmica
Fueron incorporándose a los curriculum de ciencias de la computación de diferentes universidades -
J. Hartmanis and R.E. Stearns
Introducen la noción fundamental de medida de complejidad definida como el tiempo de computación sobre una máquina de Turing multicinta. -
Norman E. Gibbs y Allen B. Tucker
Indican que: ‘no debemos
entender que el objetivo de las Ciencias de la Computación sea la
construcción de programas sino el estudio sistemático de los algoritmos y estructura de datos, específicamente de sus propiedades formales’. -
A. Berztiss. Ciencias de la Computación.
Se consideran las Ciencias de la
computación, como un cuerpo de conocimiento cuyo objetivo es obtener respuestas para las siguientes cuestiones:
A) ¿Qué problemas se pueden resolver mediante un computador?
B) ¿Cómo puede construirse un programa para resolver un problema?
C) ¿Resuelve realmente nuestro programa el problema?
D) ¿Cuánto tiempo y espacio consume nuestro problema?