Introducción a la computación: Modelos teóricos, ordenadores digitales y redes neuronales

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 no solo en el desarrollo

teórico de las C.C., sino que muchos aspectos de la práctica de la computación que son

ahora lugar común de los informáticos, fueron presagiados por ellos; incluyendo la existencia

de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre

software y hardware, y la representación de lenguajes por estructuras formales basados en reglas

de producción.

El punto de partida de estos primeros trabajos fueron las cuestiones fundamentales que D.

Hilbert formuló en 1928, durante el transcurso de un congreso internacional:

1.- ¿Son completas las matemáticas, en el sentido de que pueda probarse o no cada aseveración

matemática?

2.- ¿Son las matemáticas consistentes, en el sentido de que no pueda probarse simultaneamente

una aseveración y su negación ?

3.- ¿Son las matemáticas decidibles, en el sentido de que exista un método denido que se pueda

aplicar a cualquier aseveración matemática, y que determine si dicha aseveración es cierta?.

La meta de Hilbert era crear un sistema matemático formal çompleto 2 çonsistente", en el que

todas las aseveraciones pudieran plantearse con precisión. Su idea era encontrar un algoritmo que

determinara la verdad o falsedad de cualquier proposición en el sistema formal. A este problema

le llamó el `Entscheidungsproblem'.

Por desgracia para Hilbert, en la década de 1930 se produjeron una serie de investigaciones

que mostraron que esto no era posible. Las primeras noticias en contra surgen en 1931 con K.

Gödel y su 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."

Como consecuencia no será posible encontrar el sistema formal deseado por Hilbert en el

marco de la lógica de primer orden, a no ser que se tome un conjunto no recursivo de axiomas,

hecho que escapaba a la mente de los matemáticos. Una versión posterior y más general del

teorema de Gödel elimina la posibilidad de considerar sistemas deductivos más potentes que los

sistemas de primer orden, demostrando que no pueden ser consistentes y completos a la vez.

Un aspecto a destacar dentro del teorema de incompletitud de Gödel, fué la idea de codi-

cación. Se indica un método (numeración de Gödel) mediante el cual se asigna un número de

código (entero positivo) a cada fórmula bien formada del sistema (fbf) y a cada sucesión nita

de fórmulas bien formadas, de tal modo que la fbf o sucesión nita de fbf se recupera fácilmente

a partir de su número de código. A través de este código, los enunciados referentes a enteros

...