La Teoría de la
Computabilidad es la rama de las ciencias de la computación que consiste en
encontrar maneras de representar descripciones de procesos, de tal manera que
se pueda asegurar si existe o no una representación. Se dice que un algoritmo
es una manera formal y sistemática de representar la descripción de un proceso.
La Teoría de la
Computabilidad es el estudio matemático de los modelos de computación.
Como tal estudio teórico, se originó en la década de los años 30 con los
trabajos de los lógicos Church, Gödel, Kleene, Post y Turing.
El propósito inicial de
la teoría de la computabilidad 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. 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... Surge así una teoría que producirá
resultados positivos y negativos (estamos pensando en resultados de no
computabilidad o de indecibilidad).
Historia
de la teoría de la computabilidad
El origen de los
modelos abstractos de computación se encuadra en los años 1930 (antes de que
existieran los ordenadores modernos), para el trabajo de los lógicos Alonzo
Church, Kurt Gödel, Stephen Kleene, Emil Leon Post, y Alan
Turing. Estos trabajos iniciales han tenido una profunda influencia, tanto en
el desarrollo teórico como en abundantes aspectos de la práctica de la
computación. El punto inicial de estos primeros trabajos fueron las cuestiones
fundamentales que David Hilbert formuló en 1900, durante el
transcurso de un congreso internacional.
Lo que Hilbert
pretendía era crear un sistema matemático formal completo y
consistente en el cual todas las aseveraciones fueran planteadas con precisión,
lo cual no pudo lograr hacer. Pero fueron otros los que mediante una serie de
investigaciones mostraron que esto no era posible. En contra de esta idea K.
Gödel sacó a la luz su conocido Primer Teorema de Incompletitud. Este
viene a expresar que todo sistema de primer orden consistente que contenga
los teoremas de la aritmética y cuyo conjunto de axiomas sea recursivo no
es completo.
Máquinas
de Turing
Uno de los primeros
modelos matemáticos de una computadora fue desarrollado por Alan Turing. Este
modelo, llamado máquina de Turing, es un dispositivo extremadamente simple que
captura por completo nuestra noción de computabilidad.
La entrada a la máquina
es una cinta sobre la cual se ha escrito la entrada. Usando un cabezal de
lectura/escritura, la máquina convierte la entrada en salida a través de una
serie de pasos. En cada paso, se toma una decisión sobre si y qué escribir en la
cinta y si se debe mover hacia la derecha o hacia la izquierda. Esta decisión
se basa exactamente en dos cosas: El símbolo actual debajo del cabezal y El
estado interno de la máquina, que también se actualiza cuando se escribe el
símbolo.
Universalidad
y problemas no computables
Una de las técnicas más
usadas en esta teoría ha sido la codificación de los algoritmos utilizando el
método de la codificación de Gödel. Como ya hemos comentado, esto nos va a
permitir ver a los algoritmos cuyas entradas sean números naturales como algoritmos
cuyas entradas sean algoritmos. Esta fué la técnica usada por Church, Kleene y
Turing para encontrar problemas sin solución, técnica que por otro lado ha dado
lugar a muy fructíferos resultados en cuestiones generales acerca de los
algoritmos.
De esta forma se
demostró que era posible construir una máquina de propósito general, es decir,
capaz de resolver cualquier problema que se pudiese resolver mediante un
algoritmo. Dicha máquina tendría como entrada el entero que codificaría el
algoritmo solución del problema y la propia entrada del problema, de tal forma,
que la máquina aplicaría el algoritmo codificado a la entrada del problema.
Esta hipotética máquina puede considerarse como el padre de los actuales
ordenadores de proposito general.
Decidibilidad
e indecidibilidad
La teoría de la
computabilidad estudia los problemas que pueden ser resueltos por una máquina
de Turing y cuáles no.
Un problema es indecidible
cuando no existe un algoritmo para una máquina de Turing que pueda resolverlo.
Un problema es
decidible cuando existe un algoritmo para una máquina de Turing que lo pueda
resolver.
Problemas
que requieren mayor poder de cómputo
Se considera que
algunas máquinas tienen mayor poder que las máquinas de Turing. La teoría
de cómputos reales estudia máquinas con precisión absoluta en los números
reales. Dentro de esta teoría, es posible demostrar afirmaciones interesantes,
tales como «el complemento de un conjunto de Mandelbrot es solo
parcialmente decidible».
Conclusión
En nuestra vida
profesional e incluso en nuestro día a día, podemos encontrarnos con problemas
nunca antes vistos y podemos usar herramientas y técnicas probadas para
determinar el mejor curso de acción.
