6 Modelos de Computación I

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

...