Karlo

Complejidad y Computabilidad
La ciencia de la computación es un cuerpo sistematizado del conocimiento concerniente al cálculo, que se sostiene en dos áreas fundamentales: La Teoría de laComputabilidad, basada en las ideas y los modelos fundamentales subyacentes al cálculo, y las técnicas de la ingeniería para el diseño de algoritmos. Este artículo está pensando en la importancia del primeraspecto. La Teoría de la Complejidad computacional estudia los recursos requeridos para resolver un problema como son el tiempo y el espacio; por su parte la teoría de la computabilidad se interesa enexpresar los problemas como algoritmos sin tener en cuenta la información sobre los recursos necesarios para ello.
Para abstraer las variaciones entre los diferentes sistemas computacionales seutiliza una máquina de
Turing como un referente fijo, considerado como un modelo de máquina isofórmica a cualquier otro sistema informático.

La Tesis de Church-Turing nos dice que si la máquina deTuring no puede resolver un problema, ninguna otra computadora podrá hacerlo, puesto que no existe algoritmo para resolver el problema. Por esa razón, las limitaciones corresponderían a los procesoscomputacionales y no a la tecnología.
Es conveniente suponer que un sistema computacional es fijo (abstracto), con la finalidad
de eliminar las variaciones de un sistema a otro.

Brookshear eliminaestas variaciones de análisis en sistemas diferentes y evalúa la complejidad de cálculosuponiendo un sistema fijo basado en una máquina de Turing, ya que supone que a partir de
ella puede trasladarsus resultados a otros sistemas y mantener la complejidad.

La Teoría de la Complejidad Computacional se basa en un enfoque no funcional, en donde interesa
como se lleva el cálculo y sucomplejidad en función de los recursos que utiliza. La Teoría de la
Computabilidad se interesa en hallar una solución a un problema, mas no se interesa por los métodos
específicos de expresar una solución...