LA TESIS DE CHURCH-TURING

Una vez que nos hemos empezado a familiarizar con la construcción de las máquinas de Turing sencillas, resulta fácil convencerse de que las distintas operaciones aritméticas básicas, tales como la suma de dos números, su multiplicación o la elevación de uno a la potencia del otro, pueden ser efectuadas por máquinas de Turing concretas. No sería demasiado complicado explicarlo, pero prefiero no hacerlo en este momento. También pueden darse operaciones cuyo resultado sea un par de números naturales, tales como la división con resto u otras en las que el resultado es un conjunto finito pero arbitrariamente grande de números. Por otra parte, pueden construirse máquinas de Turing para las que no se especifique por adelantado qué operación matemática hay que realizar, sino que las instrucciones para ello estén incluidas en la cinta. Pudiéndose dar el caso de que la operación que haya que realizar en una etapa dependa del resultado de algún cálculo que la máquina tenga que hacer con anterioridad. («Si la respuesta a ese cálculo es mayor que tal y tal, hacer esto; en caso contrario, hacer lo otro»).

Una vez que nos damos cuenta de que se pueden construir máquinas de Turing que realizan operaciones aritméticas, o simplemente lógicas, es fácil imaginar en qué forma podrían construirse para realizar tareas más complicadas de naturaleza algorítmica. Cuando se ha jugado un rato con tales cosas se convence uno de que puede construirse una máquina de este tipo para realizar ¡cualquier operación mecánica! Desde el punto de vista matemático, podemos definir una operación mecánica que pueda ser llevada a cabo por una máquina como la de Turing. El sustantivo «algoritmo» y los adjetivos «computable», «recursivo» y «efectivo» son todos ellos usados por los matemáticos para denotar las operaciones mecánicas que pueden ser realizadas por máquinas teóricas de este tipo. Desde el momento que un procedimiento es suficientemente claro y mecánico, resulta razonable creer que se puede encontrar una máquina de Turing que realmente lo realice. Este era, después de todo, el objetivo de nuestra (más bien, la de Turing) discusión introductoria motivada por el concepto de máquina de Turing.

Por otro lado, podría parecer que el diseño de estas máquinas es innecesariamente restrictivo. Imponer que el dispositivo sólo pueda leer cada vez un dígito binario (0 o 1), y moverse solamente un espacio cada vez a lo largo de una única cinta unidimensional parece limitante a primera vista. ¿Por qué no permitir cuatro o cinco, o quizá mil cintas separadas, con un gran número de dispositivos de lectura interconectados y funcionando todos a la vez? ¿Por qué no permitir todo un plano de cuadros con 0's v 1's (o quizá una disposición tridimensional) en lugar de insistir en una cinta unidimensional? ¿Por qué no permitir símbolos de un alfabeto o de un sistema de numeración más complicado? De hecho, ninguno de estos cambios supone la más mínima ganancia en cuanto a los resultados, aunque alguno de ellos pueda suponer cierta diferencia en cuanto a la economía de las operaciones (como ciertamente sería el caso si permitiéramos más de una cinta). ¡La clase de operaciones realizables, y que por consiguiente caen bajo el rubro de «algoritmos» («cómputos» o «procedimientos efectivos» u «operaciones recursivas»), sería exactamente la misma que antes aunque ampliáramos la definición de nuestras máquinas con todas estas modificaciones a la vez!

Veamos que no hay necesidad de más de una cinta, con tal que el dispositivo siga encontrando en ella tanto espacio como necesite. Para ello tal vez sea necesario cambiar datos de un lugar a otro de la cinta. Esto puede ser «ineficiente» pero no limita las posibilidades del dispositivo.^[2.6] Análogamente, en principio no se gana nada (aunque, en ciertas circunstancias, pueda conseguirse una mayor velocidad de cómputo) utilizando más de un dispositivo de Turing en acción paralela —una idea que se ha puesto de moda en los últimos años con los intentos de modelar más exactamente el cerebro humano—. Al tener dos dispositivos separados que no se comunican directamente no se consigue más de lo que se obtiene con dos que sí se comuniquen; pero si se comunican entonces son, de hecho, un solo dispositivo.

¿Y qué sucede con la restricción de Turing de tener una cinta unidimensional? Si pensamos que esta cinta representa el «entorno», preferiríamos considerarlo, más que como una cinta unidimensional, como una superficie plana, o quizá como un espacio tridimensional. Una superficie plana parecería estar más próxima a lo que necesita un «diagrama de flujo» (como en la anterior descripción del algoritmo de Euclides) que una cinta unidimensional.^[2.7] No obstante, en principio no hay dificultad alguna para escribir la operación de un organigrama en forma «unidimensional» (v.g. mediante una descripción verbal del diagrama). La representación plana bidimensional se hace sólo en nombre de nuestra propia conveniencia y facilidad de comprensión y no supone diferencia alguna en los resultados. Siempre es posible codificar el lugar de una marca o un objeto en un plano bidimensional —o incluso en un espacio tridimensional— sobre una cinta unidimensional. (De hecho, utilizar un plano bidimensional es completamente equivalente a utilizar dos cintas. Las dos cintas proporcionarían las dos «coordenadas» que serían necesarias para especificar un punto en el plano bidimensional; de modo análogo tres cintas pueden actuar como «coordenadas» de un punto en un espacio tridimensional). Una vez más, esta codificación unidimensional puede ser «ineficiente» pero no limita las posibilidades.

Pese a todo esto podríamos aún preguntarnos si el concepto de máquina de Turing engloba realmente todas las operaciones lógicas o matemáticas que llamaríamos «mecánicas». Cuando Turing escribió su artículo original todo esto era mucho menos claro de lo que es hoy, así que creyó necesario presentar sus argumentos con gran detalle. Lo que Turing postulaba rigurosamente encontró apoyo adicional en el hecho de que, en forma independiente (y en realidad un poco antes), el lógico estadounidense Alonzo Church (con la ayuda de S. C. Kleene) había desarrollado un esquema —el cálculo lambda— dirigido también a resolver el Entscheidungsproblem de Hilbert. Aunque este esquema mecánico omnicomprensivo no resultaba tan obvio como el de Turing, tenía algunas ventajas en la sorprendente economía de su estructura matemática. (Describiré el notable cálculo de Church al final de este capítulo). Hubo aún otras propuestas para resolver el problema de Hilbert también independientemente de Turing (véase Gandy, 1988), muy en particular la del lógico polaco-estadounidense Emil Post (un poco después que Turing, pero con ideas mucho más afines a las de Turing que a las de Church). Pronto se demostró que todos estos esquemas eran completamente equivalentes. Esto reforzó considerablemente la idea, que se llegó a conocer como Tesis de Church-Turing, de que el concepto de máquina de Turing (o sus equivalentes) definía realmente lo que, en matemáticas, entendemos por procedimiento algorítmico (o efectivo o recursivo o mecánico). Ahora que las computadoras electrónicas de alta velocidad han llegado a ocupar un lugar tan importante en nuestras vidas cotidianas, poca gente parece sentir la necesidad de cuestionar esta tesis en su forma original. En lugar de ello, se ha dirigido la atención al dilema de si los sistemas físicos reales (incluyendo los cerebros humanos) —sujetos como están a leyes físicas precisas— son capaces de realizar más, menos o exactamente las mismas operaciones lógicas y matemáticas que las máquinas de Turing. Personalmente, acepto de buen grado la forma matemática original de la Tesis de Church-Turing. Por otro lado, su relación con el comportamiento de los sistemas físicos reales es un tema aparte que ocupará nuestra atención más adelante en este libro.