TEORÍA DE LA COMPLEJIDAD COMPUTACIONAL Y TEORÍA DE LA COMPUTABILIDAD

Autores/as

  • Augusto Cortéz Vásquez

Palabras clave:

Complejidad computacional, computabilidad, eficiencia de algoritmos.

Resumen

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 la Computabilidad, 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 primer aspecto. 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 en expresar 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 se utiliza 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 de Turing 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 procesos computacionales y no a la tecnología.

Descargas

Los datos de descarga aún no están disponibles.

Descargas

Archivos adicionales

Publicado

2004-12-30

Número

Sección

Artículos

Cómo citar

[1]
“TEORÍA DE LA COMPLEJIDAD COMPUTACIONAL Y TEORÍA DE LA COMPUTABILIDAD”, Rev.Investig.sist.inform., vol. 1, no. 1, pp. 102–105, Dec. 2004, Accessed: Mar. 28, 2024. [Online]. Available: https://revistasinvestigacion.unmsm.edu.pe/index.php/sistem/article/view/3216