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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

teSIS cHurcH–turINg

Existe un obstáculo importante al probar que no existe un algoritmo para una tarea específica. Pri-
mero es necesario saber con exactitud qué significa algoritmo. Cada uno de los matemáticos men-
cionados en la sección anterior había superado este obstáculo definiendo dicho vocablo de forma
diferente:

• Gödel definió un algoritmo como una secuencia de reglas para formar funcio-
nes matemáticas complicadas a partir de funciones matemáticas más simples.

• Church utilizó un formalismo denominado cálculo lambda.

• Turing empleó una máquina hipotética conocida como máquina de Turing. Tu-
ring definió un algoritmo como cualquier conjunto de instrucciones para su máqui-
na simple (Dasgupta, Papadimitriou y Vazirani, 2008).

Estas definiciones —en apariencia diferentes y creadas de manera independiente— resultan ser
equivalentes. Conforme los investigadores se dieron cada vez más cuenta de esta equivalencia en la
década de 1930, se creyó en forma amplia en las dos proposiciones siguientes:

1. Todas las definiciones razonables de algoritmo conocidas hasta el momento
son equivalentes.

2. Cualquier definición razonable de algoritmo que se llegue a dar, a su vez será
equivalente a las definiciones ya conocidas.

Estas creencias han llegado a denominarse tesis de Church-Turing en honor a dos de los primeros
trabajadores que se dieron cuenta de la naturaleza fundamental del concepto que habían definido.
Hasta el momento no ha existido evidencia en contra y se acepta ampliamente la tesis de Church-Tu-
ring.

En un planteamiento moderno, es posible definir algoritmo como cualquier cosa que pueda ejecutar-
se en una computadora. Dadas dos computadoras modernas, es posible escribir un programa para
una de ellas que pueda comprender y ejecutarse en otra.
La equivalencia entre toda computadora moderna, así como entre la máquina de Turing con otros
numerosos medios de definir algoritmo, es una evidencia más de la tesis de Church-Turing. Esta
propiedad de los algoritmos se conoce como universalidad.

169