El desarrollo formal de la teoría de la computación se originó casi cincuenta años antes de que apareciera el primer ordenador digital, el ENIAC (1945) diseñado por John Eckert y John Mauchly (con objeto de calcular trayectorias balísticas). Sus raíces se encuentran en los trabajos de Hilbert, Gödel, Rosser, Kleene, Church, Turing y Post, sobre la potencia del razonamiento matemático con respecto a un problema computacional, propuesto por el alemán David Hilbert, hace más de 90 años. Este problema, llamado el Problema de Decisión (Entscheidungsproblem), se puede establecer de una manera informal:
Breve historia de la Computación
(Gp:) Dada una representación formal de una afirmación (enunciado) matemática, diseñar un algoritmo (programa) que determine si la afirmación es verdadera (teorema) o falsa (no válida lógicamente).
David Hilbert (1862-1943)
Si tal programa existe, cualquier conjetura se puede probar o refutar expresándola formalmente y construyendo mecánicamente una demostración, de manera que todo el razonamiento matemático se basa en un fundamento lógico, donde todos los enunciados (afirmaciones) ciertos son demostrables (al igual que los falsos) y cada afirmación es verdadera o falsa. Así cualquier teoría matemática estaría formada por un conjunto de axiomas y un conjunto de reglas de inferencia que permiten generar enunciados válidos adicionales a partir de enunciados válidos dados. La verdad de cada axioma se admite a priori.
Dicho programa se puede escribir si se puede encontrar un conjunto de axiomas que:
sean lo suficientemente potentes para permitir que se pueda probar cualquier enunciado verdadero, y que
no admitan contradicciones, es decir, que una afirmación y su negación no puedan ser ciertas al mismo tiempo.
En 1931, el matemático austriaco Kurt Gödel publica su famoso teorema de incompletitud que establece que no puede existir un conjunto de axiomas con las dos propiedades anteriores y, por lo tanto, el programa anterior no se podrá escribir. Más concretamente:
(Gp:) "Ningún sistema de razonamiento matemático es lo suficientemente potente para ser capaz de probar toda afirmación cierta acerca de las propiedades de los números naturales".
Kart Gödel (1906-1978)
La Teoría de la Computabilidad se ocupa de construir un formalismo matemático para razonar sobre la existencia o no existencia de algoritmos efectivos para problemas particulares. Los resultados que se prueben dentro de esta teoría deben ser aplicables a todas las arquitecturas de ordenadores, independientemente de sus parámetros, como pueden ser la velocidad del procesador o el tamaño de la memoria. Para ello tiene como base el concepto de modelo de computación.
Necesitamos saber qué entendemos por algoritmo efectivo y por problema. Aunque el desarrollo formal de la teoría de la computabilidad se realiza en el siglo XX, sin embargo la búsqueda de algoritmos efectivos para resolver ciertos problemas se viene realizando desde hace más de 2000 años.
Los matemáticos griegos, como se comprueba en los trabajos de Euclides y Pitágoras, pusieron gran énfasis en las técnicas constructivas. Así, en geometría se plantearon algunos problemas que dejaron sin resolver y que han constituido materia de investigación durante mucho tiempo, como:
El problema de la cuadratura del circulo:
"Dado un circulo, construir un cuadrado con la misma área utilizando regla y compás“
El problema de la trisección de un ángulo:
"Dividir un ángulo dado en tres partes iguales mediante regla y un compás".
El problema de la duplicación del cubo:
"Dado un cubo, construir otro con exactamente el doble de volumen que el original, utilizando regla y compás".
En este contexto, un algoritmo efectivo será aquel que emplee en sus pasos de computación sólo regla y compás. Sin embargo, hoy se sabe que ninguno de estos problemas tiene solución. Por lo tanto, no existe un método de construcción apropiado y así no pueden existir tales algoritmos.
La longitud de cualquier segmento construido usando regla y compás se puede escribir como una expresión en la que intervienen los números naturales y las operaciones +, , y .
La duplicación del cubo es imposible pues se precisa construir un segmento de longitud 21/3 (Descartes, 1637).
La trisección del ángulo requiere construir líneas cuyas longitudes vienen dadas por las raíces de un polinomio cúbico. Para ciertos ángulos, como los de 60º estas longitudes no son expresables en la forma requerida (Descartes, 1637).
Lindemann probó en 1882 que el número es trascendente y como cualquier solución deberá construir un segmento de longitud , no existe un algoritmo válido para su construcción.
En un programa de ordenador se genera una salida utilizando la entrada leída. Así, cualquier programa se puede considerar como un evaluador de una función, f, que aplica algún dominio de valores de entrada, I, en algún rango de valores de salida, O.
La cuestión que surge ahora es:
¿Qué problemas se pueden resolver con programas de ordenador?
Es decir,
¿Qué funciones se pueden computar?
Para establecer una formulación rigurosa de lo que entendemos por algoritmo efectivo y por problema necesitamos dar los siguientes conceptos:
Un alfabeto es cualquier conjunto finito no vacío; un símbolo (o letra) es un elemento del alfabeto; una palabra es una secuencia o cadena finita de símbolos de y la longitud de una palabra x de *es el número de símbolos que la forman.
Dos palabras x e y de serán iguales si y sólo si tienen todos los términos iguales; esto es, si y sólo si tienen las mismas letras en las mismas posiciones.
El conjunto infinito de todas las palabras que se pueden formar con símbolos de se representa por
En el conjunto de las palabras del alfabeto se define una operación llamada concatenación de palabras de la manera siguiente:
Dadas las palabras x = a1 a2 …an e y = b1 b2 …bm, la concatenación es la palabra
xy = a1 a2 …an b1 b2…bm
Llamaremos lenguaje sobre un alfabeto a cualquier subconjunto L de
Cualquier orden entre los símbolos de induce un orden entre las palabras de n de la siguiente manera:
1. Para cada n, las palabras de longitud n preceden a las palabras de longitud n+1.
2. Para las palabras de igual longitud se establece el orden alfabético.
A este orden se le llama orden lexicográfico. Como consecuencia de este orden podemos enumerar todas las palabras del lenguaje. Es decir, cualquier lenguaje sobre es un conjunto numerable.
También podemos establecer funciones f :
Un problema de decisión es una función cuyo resultado es 0 ó 1 (falso o verdadero). Por lo tanto, todas las funciones
son problemas de decisión
Ejemplo: Problema de decisión de la paridad de un número natural expresado en base dos.
El alfabeto es el conjunto {0,1} y cada palabra corresponde a un número natural expresado en base dos. En este caso f(x) vale 1 si x corresponde a un número par, es decir, si la palabra x termina con el símbolo 0. Así,
f(010110) = 1 y f(11001) = 0.
Dado cualquier problema de decisión, el conjunto queda dividido en dos conjuntos disjuntos:
y
que son el lenguaje correspondiente a f y su lenguaje complementario
Ejemplo:
El lenguaje correspondiente al problema de decisión de la paridad es:
L(f) = {0, 00, 10, 000, 010, 100, 110,….}
Hemos sustituido la idea vaga de resolución del problema por el concepto preciso de determinar si una palabra de entrada dada es un elemento de un conjunto particular de palabras.
Así, determinar si un número natural escrito en binario es par es equivalente a decidir si dicho número se encuentra en el conjunto
{0, 00, 10, 000, 010, 100, 110,….}
Los modelos formales de computación que vamos a estudiar nos suministran un conjunto de operaciones básicas para manipular los datos de entrada y obtener los datos de salida. Así, en un modelo de computación cualquiera, un algoritmo efectivo, para un problema de decisión dado, f, es una secuencia de operaciones (permitidas) que determina si una palabra cualquiera x está (o no) en L(f). Se dirá que tal algoritmo (programa) reconoce el lenguaje L(f).
La Teoría de la Computabilidad se ocupa de dividir el universo de todos los lenguajes sobre , en aquellos lenguajes que pueden ser reconocidos por algoritmos efectivos y los que no. Ello conduce a las funciones no computables, es decir, a los problemas no resolubles.
Vamos a recordar algunos modelos clásicos (máquinas) de computación, como las máquinas de Turing (determinística y no determinísticas) y los autómatas celulares que conducen a diferentes formalizaciones del concepto de algoritmo, todas ellas equivalentes (equivalentes también a otras formalizaciones ideadas por Kleene, Church, Post, etc.). Esta equivalencia refuerza la Tesis de Church-Turing que afirma:
(Gp:) “la clase de problemas que se pueden resolver utilizando el sistema de programación de Turing es exactamente el mismo que los que se pueden resolver utilizando cualquier sistema de programación razonable”
La teoría clásica de la Computabilidad trata de determinar qué problemas algorítmicos se pueden resolver por ordenador en condiciones ideales de disposición ilimitada de memoria y tiempo. Las máquinas de Turing han sido aceptadas como modelos estándar para el estudio de la computabilidad durante más de medio siglo. Comenzaremos analizando el modelo más simple de máquinas de estados finitos.
Las máquinas de estados finitos fueron introducidas formalmente por Rabin y Scott (1959). Una máquina de estados finitos consta de un dispositivo de memoria representado por una colección finita de estados y de una función de transición que actualiza el estado actual como una función del estado previo y de la entrada en curso. Se supone que toda la información viene codificada por cadenas de símbolos (caracteres) de un alfabeto fijo, que constituyen la entrada a la máquina. Una formalización sencilla de una máquina de estados finitos es el autómata finito.
De la computabilidad clásica a las Redes Neuronales
Un autómata finito determinístico es una quíntupla M = (K, ?, ?, s, F),
K es un conjunto finito de estados
? es un alfabeto
s?K es el estado inicial
F?K es el conjunto de estados finales
? es una función de K?? en K,
llamada función de transición
Un autómata finito determinístico funciona de la siguiente manera: la información que recibe la máquina viene codificada en símbolos de un alfabeto que se escriben en una cinta de entrada divida en cuadrados (en número ilimitado) y se escribe un símbolo en cada cuadrado (casilla). La parte principal de la máquina es una “caja negra”, llamada unidad de control finita, que presenta, en cada momento específico, un estado concreto del conjunto de estados posibles K. La unidad de control finita puede leer el símbolo escrito en la casilla correspondiente de la cinta de entrada mediante una cabeza de lectura movible. Inicialmente, la cabeza grabadora se coloca al comienzo de la cinta y la unidad de control finito se encuentra en el estado inicial.
(Gp:) ?
(Gp:) K
?
A continuación el autómata lee el símbolo de la primera casilla y la unidad de control finito pasa a un nuevo estado que viene especificado por su función de transición; el nuevo estado depende del estado previo y del símbolo leído. Entonces la cabeza de lectura se mueve una casilla a la derecha y lee el símbolo escrito en dicha casilla. Este proceso se va repitiendo a intervalos regulares, se lee un símbolo, la unidad de control finito actualiza su estado y la cabeza de lectura pasa a la casilla siguiente, así sucesivamente hasta que la cabeza de lectura llega al final de la cadena de símbolo escritos en la cinta de entrada. El autómata acepta (aprueba),o no (desaprueba), la cadena de símbolos de entrada (palabra) según que el estado que presenta la unidad de control finito sea, o no, un estado del conjunto final de estados F. El conjunto de palabras (cadenas de símbolos) que acepta un autómata finito determinístico constituye el lenguaje aceptado por la máquina.
Ahora surge la siguiente cuestión: ¿qué propiedades tienen los lenguajes aceptados por un autómata finito determinista?
Se puede demostrar que son cerrados bajos las siguientes operaciones unión, intersección, complementación, concatenación y la operación clausura (estrella de Kleene). Por lo tanto, son los lenguajes regulares.
Una posible generalización de los autómatas finitos determinísticos es sustituir la función de transición ? por una relación de transición ? que es un subconjunto finito de ???*??, donde ?* es el conjunto de todas las cadenas finitas que se pueden formar con símbolos del alfabeto ?, incluyendo la cadena vacía. Es decir, ahora se permiten varios estados siguientes para un símbolo de entrada dado y un estado previo de la unidad de control. A este tipo de máquinas se le llama autómatas finitos no deterministas. Sin embargo, estas maquinas son equivalentes a los autómatas finitos determinísticos, es decir, aceptan los mismos lenguajes. Además, para cada autómata finito no deterministico se puede construir un autómata finito determinístico equivalente.
Sin embargo, los autómatas finitos determinísticos no se pueden considerar como modelos verdaderamente generales para el diseño de computadores puesto que no son capaces de reconocer lenguajes tan simples como L = { an bn cn : n?Z+ }. Por ello, es necesario introducir nuevos mecanismos que puedan reconocer estos lenguajes y lenguajes mucho más complicados.
Uno de estos dispositivos más potentes es la máquina de Turing que fue ideada por Alan Turing (1912-1954). La máquina de Turing consta de una unidad de control finito, de una cinta y de una cabeza grabadora que puede usarse para leer o para escribir sobre la cinta. Una máquina de Turing no determinística es una cuádrupla M = (K, ?, ?, s), en la que
K es un conjunto finito de estados, que no contiene al estado de parada h.
? es un alfabeto que contiene el símbolo blanco ?, pero no contiene los símbolos L y R.
s?K es el estado inicial
? es una función de K?? en (K?{h})?(??{L,R}) , llamada función de transición.
Para estudiar si una función es o no computable, utilizaremos la máquina de Turing. Consideramos dos alfabetos ?o y ?1 y una f definida de
Página siguiente  |