lección

LECCION 1. - INTRODUCCION E HISTORIA1
oy en día parece que no existe ningún límite a lo que un computador puede
llegar a hacer, y da la impresión de que cada vez se pueden resolver nuevos y
más difíciles problemas.
El hombre ha tratado de buscar procedimientos y máquinas que le faciliten la
realización de cálculos (aritméticos primero, y otros más complejos
posteriormente).
El avancetecnológico para representar datos y/o información por un lado, y el
diseño de nuevas formas de manejarlos, propician el desarrollo de dispositivos y
máquinas de calcular.
Un aspecto importante en el desarrollo de los computadores, es sin duda, su
aplicación para resolver problemas científicos y empresariales. Esta aplicación
hubiese resultado muy difícil sin la utilización de procedimientos quepermiten
resolver estos problemas mediante una sucesión de pasos claros, concretos y
sencillos, es decir algoritmos. El avance de las matemáticas permite la utilización
de nuevas metodologías para la representación y manejo de la información.
Por otro lado, aparece el intento de los matemáticos y científicos para obtener un
procedimiento general para resolver cualquier problema (matemático)claramente
formulado. Es lo que podríamos llamar El problema de la computación teórica.
El avance de la tecnología y de las matemáticas, y más en concreto de la teoría de
conjuntos y de la lógica, permiten plantearse aspectos de la computación en 3
caminos.
a) Computación teórica. Autómatas, Funciones Recursivas, ...
b) Computadores digitales. Nuevas tecnologías, nuevos lenguajes
c) Intentosde modelizar el cerebro biológico
1. Redes Neuronales (intentan modelizar el "procesador")
2. Conjuntos y Lógica Difusa (representar y manejar la información)
Uno de los principales factores determinantes de la profunda revolución
experimentada en el ámbito de la ciencia, la técnica y la cultura de nuestros días
es el desarrollo de la informática. La palabra ‘informática’ (Informaciónautomática), es un nombre colectivo que designa un vasto conjunto de teorías y
1 MORAL CALLEJÓN Serafín Teoría de autómatas y lenguajes formales, En:
http://decsai.ugr.es/~smc/docencia/mci/automata.pdf
NAVARRETE SÁNCHEZ, Isabel y otros Teoría de autómatas y lenguajes formales En:
http://perseo.dif.um.es/%7Eroque/talf/Material/apuntes.pdf
técnicas científicas desde la matemática abstracta hasta laingeniería y la gestión
administrativa cuyo objeto es el diseño y el uso de los computadores. Pero el
núcleo teórico más sólido y fundamental de todo ese conjunto de doctrinas y
prácticas es la llamada ‘Teoría de la Computabilidad’, formalmente elaborada en
los años 30 y 40 gracias a los descubrimientos de lógicos matemáticos como
Gödel, Turing, Post, Church, y Kleene, aunque sus orígenes másremotos datan
de antiguo, con el planteamiento de la cuestión de saber si, al cabo de cierto
esfuerzo, el hombre podría llegar a un extremo en la investigación en que,
eventualmente, toda clase de problemas pudiera ser atacado por un
procedimiento general de forma que no requiriera el más leve esfuerzo de
imaginación creadora para llevarlo a cabo. Si todo queda determinado así en
detalle,entonces sería obviamente posible abandonar la ejecución del método a
una máquina, máxime si la máquina en cuestión es totalmente automática. Esta
idea, ambiciosa sin duda, ha influido poderosamente en diferentes épocas el
desarrollo de la ciencia.
El propósito inicial es hacer precisa la noción intuitiva de función calculable; esto
es, una función cuyos valores pueden ser calculados de formaautomática o
efectiva mediante un algoritmo, y construir modelos teóricos para ello (de
computación). Así podemos obtener una comprensión más clara de esta idea
intuitiva; y solo de esta forma podemos explorar matemáticamente el concepto de
computabilidad y los conceptos relacionados con ella, tales como decibilidad, etc...
La teoría de la computabilidad puede caracterizarse, desde el punto...