6 Modelos de Computación I
Enviado por milpuertas • 27 de Julio de 2013 • 5.823 Palabras (24 Páginas) • 488 Visitas
6 Modelos de Computación I
Hoy en día parece que no existe ningún límite a lo que un ordenador puede llegar a hacer, y
da la impresión de que cada vez se pueden resolver nuevos y más difíciles problemas.
Casi desde que aparece sobre La Tierra, el hombre ha tratado de buscar procedimientos y má-
quinas que le facilitasen la realización de cálculos (aritméticos primero, y otros más complejos
posteriormente).
El avance tecnológico para representar datos y/o información por un lado, y el diseño de
nuevas formas de manejarlos, propicia el desarrollo de dispositivos y máquinas de calcular.
Un aspecto importante en el desarrollo de los ordenadores, es sin duda, su aplicación para
resolver problemas cientícos y empresariales. Esta aplicación hubiese resultado muy difícil sin
la utilización de procedimientos que permiten resolver estos problemas mediante una sucesión
de pasos claros, concretos y sencillos, es decir algorítmos. 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ícos para obtener un procedimiento
general para poder 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) Ordenadores digitales. Nuevas tecnologías, nuevos lenguajes, ....
c) Intentos de modelizar el cerebro biológico
1. Redes Neuronales (intentan modelizar el "procesador")
2. Conjuntos y Lógica Difusa (representar y manejar la información)
En este texto veremos aspectos relativos a a) y c.1).
Considermos el problema general, bajo un planteamiento de Programación.
Desde un punto de vista global, un programa (traducido a lenguaje máquina) se puede ver
como una sucesión de ceros y unos, cuya ejecución produce una salida, que es otra serie de
ceros y unos. Si añadimos un 1 al inicio de cada cadena binaria (programa y salida), podemos
entender los programas como aplicaciones concretas de una función entre números naturales en
binario. El argumento (variable independiente) sería el programa y la función (var. dependiente)
la salida del programa.
Obviamente, el número de funciones posibles de N en N es nonumerable, mientras que el
número de posibles programas que podemos escribir con un Lenguaje de Programación, que
tiene un número nito de símbolos, es numerable.
Esto signica (cada programa puede calcular una sola función como las indicadas antes) que
existen muchas funciones para las que no podemos escribir un programa en nuestro L. de Alto
Nivel, aunque seguramente estamos interesados en resolver el problema asociado a la función.
Cap. 1 Introducción 7
Entonces nos preguntamos cosas como:
¿Para qué problemas no podemos escribir un programa ?
¿Podremos resolver algunos de estos problemas con otro lenguaje de programación y/o con
otros computadores ?.
Además, para los problemas que si tienen un programa asociado,
¿Se podrá ejecutar el programa en un ordenador actual en un tiempo razonable ? (p.e., antes
de que llegue nuestra jubilación).
¿Los ordenadores futuros podrán hacerlo ?
Trataremos de dar respuestas a algunas de estas cuestiones, a lo largo del desarrollo de la
asignatura.
1.1. Introducción Histórica
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ón automática), es un nombre colectivo que designa un
vasto conjunto de teorías y técnicas cientícas -desde la matemática abstracta hasta la ingenier
ía y la gestión administrativa- cuyo objeto es el diseño y el uso de los ordenadores. 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ás remotos 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 ídea,
ambiciosa sin duda, ha inuido 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 forma automá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 relacionadas con ella, tales como
decibilidad, etc...
La teoría de la computabilidad puede caracterizarse, desde el punto de vista de las C.C.,
como la búsqueda de respuestas para las siguientes preguntas:
1)¿Qué pueden hacer los ordenadores (sin restricciones de ningún tipo )?
2) ¿Cuales son las limitaciones inherentes a los métodos automáticos de cálculo?.
8 Modelos de Computación I
El primer paso en la búsqueda de las respuestas a estas preguntas está en el estudio de los
modelos de computación.
Los comienzos de la Teoría. La Tesis de Church-Turing
Los modelos abstractos de computación tienen su origen en los años 30, bastante antes de
que existieran los ordenadores modernos, en el trabajo de los lógicos Church, Gödel, Kleene,
Post, y Turing. Estos primeros trabajos han tenido una profunda inuencia
...