Page 177 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

las consecuencias de los teoremas de gödel

No existe un algoritmo que pueda verificar en todos los casos la verdad o falsedad de un enuncia-
do aritmético. En otras palabras, jamás se podrá programar a una computadora de modo que
pueda demostrar todas las conjeturas de la aritmética (se trata de una limitación esencial que
los avances tecnológicos no podrán superar); de hecho, las computadoras jamás superarán a los
matemáticos (aunque, como se verá más adelante, tampoco queda claro que los matemáticos sean
siempre capaces de superar a las computadoras).

computabilidad y complejidad

El estudio de la computabilidad lleva a comprender cuáles son los problemas que admiten solución
algorítmica y cuáles no. De aquellos problemas para los que existen algoritmos, también resulta de
interés saber cuántos recursos de cómputo se necesitan para su ejecución. Solo los algoritmos que
utilizan una cantidad factible de recursos resultan útiles en la práctica. El campo de la ciencia de la
computación denominado teoría de la complejidad es el que pregunta e intenta resolver cuestiones
acerca del empleo de recursos de cómputo.

En la figura 8.1 se muestra una representación pictórica del universo de problemas. Aquellos que
pueden computarse en forma algorítmica forman un subconjunto infinitesimalmente pequeño. Los
que son factiblemente computables, tomando en cuenta sus necesidades de recursos, compren-
den una diminuta porción del ya infinitesimalmente pequeño subconjunto. Sin embargo, la clase de
problemas factibles computables es tan grande que la ciencia de la computación se ha vuelto una
ciencia interesante, práctica y floreciente.

Figura 8.1. Problemas computables y no computables

171