Comput

Computabilidad de Turing
Fragmento del cap. 3 “Turing Computability” de Computability and Logic, 4ta. ed., escrito por
George S. Boolos, John P. Burgess, Richard Jeffrey. Cambridge et al., Cambridge University Press,
2002, pp. 23-26. Traducción al español de Esteban Perini y Florencia Ragone

Una función es efectivamente computable si existen determinadas reglas explícitas por las
cuales se puedaen principio computar su valor para cualquier argumento dado. Esta noción
será explicada más a fondo abajo, sin embargo, incluso después de una explicación extensa,
permanece como una noción intuitiva. En este capítulo nos dedicaremos al análisis de la
computabilidad introduciendo una noción rigurosamente definida de una función Turingcomputable. Resultará evidente desde la definición que lasfunciones Turing-computables son
efectivamente computables. La hipótesis de que, a la inversa, toda función efectivamente
computable es Turing-computable se conoce como la Tesis de Turing. Esta tesis no es evidente,
ni puede ser rigurosamente probada (pues la noción de computabilidad efectiva es intuitiva y
no es una noción rigurosamente definida), sin embargo, una gran cantidad de evidencia se haacumulado en su favor. Una pequeña parte de aquella evidencia será presentada en este
capítulo y extendida en los capítulos siguientes. Primero introduciremos la noción de máquina
de Turing, daremos ejemplos y después presentaremos la definición oficial de lo que significa
para una función ser computable por una máquina de Turing o ser Turing-computable.

Un ser suprahumano, como Zeus del capítuloanterior, podría quizás escribir la tabla entera de
valores para una función unaria en los enteros positivos escribiendo cada entrada al doble de
velocidad que la anterior, pero para un ser humano es imposible en principio completar un
proceso infinito de esta naturaleza. Afortunadamente, para los fines humanos generalmente no
necesitamos la tabla entera de valores de una función f, sino sólo losvalores de a uno por vez,
por así decir: dado un argumento n, necesitamos el valor f(n). Si es posible generar el valor f(n)
de la función f para el argumento n, cuando tal valor se necesita, entonces aquello es casi tan
bueno como tener toda la tabla completa de valores escrita de antemano.
Una función f de enteros positivos a enteros positivos se llama efectivamente computable si
puede darse unalista de instrucciones que en principio hagan posible determinar el valor f(n)
para cualquier argumento n. (Esta noción se extiende de un modo evidente a funciones binarias
y n-arias). Las instrucciones deben ser completamente determinadas y explícitas. Deberían
decirle a uno qué hacer en cada paso, y no que uno pregunte a otra persona qué hacer o que
resuelva por uno mismo qué hacer: lasinstrucciones no deberían requerir fuentes externas de
1

información ni inventiva al ser ejecutadas, de modo que uno podría esperar automatizar el
proceso de aplicación de reglas, y que sea llevado a cabo por un dispositivo mecánico.
Permanece el hecho de que no será factible en la práctica para ningún ser humano ni para
ningún dispositivo mecánico llevar realmente a cabo el cómputo para todos losvalores de n sino
sólo para un número finito de ellos: teóricamente podría ser completada en una cantidad finita
de tiempo, si nos mantuviéramos sanos, o si la máquina permaneciera en correcto
funcionamiento durante ese tiempo; pero en la práctica, moriremos o la máquina colapsará
mucho antes de que el proceso se complete. (También existe una preocupación por encontrar
suficiente espacio para almacenarlos resultados intermedios del cómputo, e incluso, una
preocupación por encontrar suficiente materia para utilizar en la escritura de aquellos
resultados: sólo hay una cantidad finita de papel en el mundo, de modo que se debería escribir
más y más pequeño sin límite; para conseguir poner en papel un número infinito de símbolos
finalmente se estaría tratando de escribir sobre moléculas, átomos,...