La tesis de Church-Turing/Interpretaciones

En esta sección se van a explicar algunas de las diversas interpretaciones que tiene la tesis de Church-Turing.

Principio Church-Turing-Deutsch

En general, la tesis de Church se considera un postulado sobre matemáticas. Esta idea proviene del hecho de que dicha tesis describe el subconjunto de las matemáticas que puede ser computado; por el contrario, la Tesis Extendida de Church-Turing define el subconjunto de las matemáticas que puede ser automatizado incuestionablemente.

En 1985, Deutsch afirma que la tesis de Church es demasiado general en comparación con algunos de los principios físicos conocidos. Deutsch propone referirse a las "funciones que de manera natural sean consideradas computables" como "funciones que puedan ser computadas por un sistema físico real", ya que de esta forma lo que se quiere expresar es mucho más concreto. Todo esto le permitió introducir la concepción del diseño de una máquina de Turing.

La idea anteriormente expuesta es innovadora e interesante ya que para nosotros no es fácil entender que algo "considerado computable de forma natural" no pueda ser computado por la naturaleza. De esta manera, Deutsch convierte la tesis en un principio llamado "Principio de Church-Turing-Deutsch" cuyo enunciado se muestra a continuación:

"Todos los sistemas físicos finitos comprensibles pueden ser simulados por una máquina de computación universal que opere en pasos finitos".

Por último, la extensión de este principio al caso cuantitativo (al que nos referiremos como “CTDP Extendido”) es sencilla:

"Todo sistema físico finito puede ser simulado por una máquina de Turing, cuyo coste es equivalente al coste polinomial"

Esta es una de las implicaciones más importantes de la Tesis de Church-Turing. Principalmente, nos vamos a fijar en la siguiente consecuencia: a partir de este momento, dado un conjunto de leyes físicas perfectamente definidas mediante el uso de experimentos, seríamos capaces de deducir a partir del CTDP, como una consecuencia directa de estas leyes, que todos los sistemas definidos mediante reglas se pueden simular usando para ello una máquina de Turing.

Es necesario destacar, que las interpretaciones clásicas de la Tesis de Church no alcanzan esta conclusión.

Tesis Física de Church-Turing (PCTT)

El enunciado de la tesis física de Church-Turing (PCTT) se muestra a continuación:

"Every function that can be physically computed can be computed by a Turing machine"

Una posible traducción podría ser: cualquier función que pueda ser físicamente computable, puede ser computada por una máquina de Turing.

En 2002 este teorema fue refutado por Willem Fouché, puesto que descubrió que las máquinas de Turing no pueden obtener todos los valores posibles, unidimensionales, de los números racionales.

Strong Church-Turing thesis (SCTT)

En 1997, Bernstein y Vazirani expusieron la tesis Strong Church-Turing (SCTT), cuyo enunciado se muestra a continuación:

"Any ‘reasonable’ model of computation can be efficiently simulated on a probabilistic Turing machine".

Es un misterio que la tesis original de Church-Turing sea equivalente a esta interpretación, aunque Turing negó dicha coincidencia.

Los estudios actuales sugieren que este enunciado es falso, puesto que no es posible capturar todas las formas de computación tanto existentes como posibles mediante un algoritmo. Por ejemplo, los protocolos interactivos no son algoritmos.

Uno de las principales razones de que se llegara a la conclusión de que dicho enunciado era falso, fue que Peter Shor demostró que el problema de factorizar los números primos se puede resolver usando un ordenador cuántico, mientras que no es posible encontrar una solución al mismo problema usando una máquina probabilística de Turing.

Las razones para por las que se acepta de forma general la “Tesis Mítica de Turing” se pueden examinar en el momento en que se estableció la Informática como una disciplina independiente en 1960. Para poder entender mejor estas razones, vamos a identificar y examinar las tres principales quejas:

• Conjetura 1: Todos los problemas computables están basados en una función. Razón: La adopción de los principios matemáticos para los conceptos fundamentales de la computación, identifican el concepto de computabilidad con la computación de funciones, al igual que con la Máquinas de Turing.

• Conjetura 2: Todos los problemas computables pueden ser descritos mediante un algoritmo. Razón: La adopción de algoritmos como conceptos generales y centrales de la Informática.

• Conjetura 3: Los computadores procesan los algoritmos. Razón: se concibe el concepto de un algoritmo para hacerlo más práctico.

Tesis de Church-Turing Extendida (ECT)

Esta tesis afirma que la máquina de Turing es tan eficiente como un computador. Es decir, si alguna función es computable por algún dispositivo hardware para una entrada de tamaño n, entonces dicha función es computable por una máquina de Turing en (T(n))k para algún k fijo (dependiente del problema).

La Tesis de Zuse-Fredkin

Esta tesis fue enunciada formalmente en 1960 por Zuse y Fredkin. A continuación, se muestra la idea principal de la misma:

"El universo es un autómata celular"

Si una persona considera que la tesis de Church es verdadera entonces no puede encontrar ninguna razón que le indica que la tesis de Zuse-Fredkin es falsa, y viceversa.

En primer lugar, partimos de que si somos capaces de probar la tesis de Zuse-Fredkin, entonces podremos deducir de manera inmediata la tesis de Church-Turing. El argumento es el siguiente:

Si el universo es una autómata celular universal (UCA, Universal Cellular Automaton), obviamente, nos encontraremos con procesos computacionales pequeños, lo que nos permitirá llegar a la conclusión de que disponemos de una serie de algoritmos que actúan sobre una región específica del espacio/tiempo del autómata.

Por otro lado, cada UCA es capaz de simular cualquier otra máquina abstracta computacional, incluyendo a la Máquina Universal de Turing.

A continuación, vamos a analizar un poco la tesis de Church-Turing para determinar por qué su aparición corrobora la tesis de Zuse-Fredkin.

La tesis de Church-Turing intenta demostrar que cada función matemática computable tiene una representación isomórfica (es decir, se encuentra representado mediante un algoritmo) en un dispositivo computacional, llamado UTM.

La tesis de Zuse-Fredkin dice, en su mayoría, lo mismo como, por ejemplo, que el Universo es un dispositivo computacional que se puede considerar como una gran máquina computacional que podemos llamar Autómata Celular (CA).

También podemos decir que la tesis de Zuse-Fredkin está expuesto indirectamente un ‘hint’ directo (o, incluso, un “corolario físico”) expuesto en la tesis de Church-Turing. ¿Por qué?

A continuación, se muestra la razón propuesta:

Toda la física, que conocemos actualmente, no es nada más que un intento por “comprender” la Realidad, para lo que se utiliza una fórmula que consiste en construir una serie de “modelos matemáticos” (o “teorías”) que explican los fenómenos que se producen en el Universo.

Pero, por otro lado, podemos decir que cualquier “fórmula” o “teoría” puede ser representada (de acuerdo con la tesis de Church) mediante una UTM.

La única forma que conocemos para “estudiar” (o “comprender”) la Realidad se basa en utilizar modelos o teorías matemáticas; he aquí la gran idea de la tesis de Zuse-Fredkin de que el Universo es una especie de dispositivo computacional, denominado, autómata celular.

La Tesis M

La tesis M dice:

Todo aquello que pueda ser calculado por una máquina (en caso de que se trabaje con datos finitos de acuerdo a un número finito de instrucciones) es computable por una máquina de Turing.

La tesis M por sí misma admite dos interpretaciones:

Si la frase "puede ser generado por una máquina" se interpreta en sentido estricto como “puede ser generado por una máquina que se base en las leyes físicas del mundo actual”.
Si la frase anterior se interpreta en sentido más amplio, de tal forma que nos abstrajéramos de si la máquina abstracta en cuestión puede o no existir en el mundo actual.

Si escogemos la segunda interpretación, entonces la tesis M es falsa. Es fácil describir máquinas abstractas, o ‘hipercomputadoras’ , que generan funciones no computables por una máquina de Turing, por ejemplo Abramson, Copeland y Proudfoot, Stewart.

Todavía no se puede determinar si la primera interpretación de la tesis M es o no cierta. Las especulaciones que se realicen sobre la posibilidad de que existan procesos físicos cuyo comportamiento se parezca a funciones no computables por la máquina de Turing se remonta al menos a las últimas cinco décadas; algunos ejemplos son: Doyle, Geroch y Hartle, Hogarth, Kreisel, etc.

De hecho, ésta es la verdadera tesitura o dilema en la veracidad de la Tesis de Church-Turing. Nosotros los humanos y nuestra computabilidad intuitiva no seríamos lo importante en el enunciado de la tesis si no nos consideráramos el ente computacionalmente más complejo. La indicación de que el superconjunto de las computabilidades no tiene porqué residir en el cerebro humano es un acierto de la tesis M.

Al no estar, al igual que la Tesis de Church-Turing, debidamente formalizada, la literatura sobre la teoría computacional de la mente humana contiene numerosas proposiciones equivalentes o similares a la tesis M, todas ellas basadas en los trabajos de Turing o Church.

Algunos investigadores opinan que la tesis M (o alguna otra equivalente) debería caracterizar, de manera informal, el concepto de procedimiento efectivo de tal forma que se pueda modificar para que sea equivalente al concepto tratado. Esta acción afecta muy especialmente a la magnitud de los procedimientos efectivos, y al hecho de que puedan ser computados por una máquina.

Para cada error cometido, el espacio conceptual que no parece contener los modelos mecánicos de la mente que no son equivalentes para las máquinas de Turing. Todavía es posible que la psicología descubra la necesidad de emplear los modelos de la percepción humana que sobrepasan a las máquinas de Turing.

Es necesario destacar que en algunos casos, es importante que el autor haga una mención especial a otros anteriores. En esta línea, se recuerda que en la literatura técnica la palabra ‘computable’ se relaciona, con frecuencia, con la definición de calculabilidad efectiva.

Por supuesto, se dice que una función es computable si y sólo si podemos encontrar un método efectivo para encontrar sus valores. De acuerdo con esto, una formulación común de la tesis de Church-Turing en la literatura técnica y en los libros suele ser:

"All computable functions are computable by Turing machine"

Algunos corolarios exponen la siguiente idea:

Por supuesto, las funciones no son computables en sentido absoluto: las funciones que no son computables por la máquina de Turing, no podrán ser computadas ni en el pasado, ni en el presente ni en el futuro por una máquina real (Boolos and Jeffrey). Esto es equivalente de nuevo a la tesis M, en el sentido de que «máquina» se refiere a «máquina real».

Dada la definición de ‘computable’ como ‘efectivamente calculable’, la tesis de Church-Turing afirma que si una función F no es computable por una máquina de Turing entonces no es computable por ninguna máquina.

Por supuesto, la decisión tomada para definir el término ‘computable’ y su aceptación del concepto de efectividad no establece la validez de la tesis M. Aquéllos que hayan optado por esta decisión terminológica han sido, simplemente, prevenidos para que describan una máquina que refute la tesis M como una función computable.

La palabra ‘mecánico’, también, en términos técnicos, se relaciona estrechamente con la efectividad y, como ya se señaló anteriormente, ‘mecánico’ y ‘efectivo’ se pueden usar indistintamente (Gandy, en 1988, estructuró la historia del uso de la palabra ‘mecánico’). Por supuesto, los siguientes postulados se pueden encontrar en la literatura técnica:

Turing propuso que una clase concreta de máquinas abstractas que podrían ejecutar algunos de los procedimientos computables ‘mecánicos’ (Mendelson).

Si reflexionamos sobre la idea anterior, observamos como remarca los atributos de Turing, no para la tesis M, pero sí para la tesis de Church-Turing.

La tesis M no es, sólo, una tesis problemática que esta relacionada estrechamente con la tesis de Church. Desafortunadamente, un error común en los escritores modernos en computabilidad consiste en mantener que los resultados de Turing, se encuentran vinculados de alguna manera con la mente humana, e incluso con cualquier sistema físico o biológico, de tal forma que pueden ser simulados mediante una máquina de Turing.

Por ejemplo, la entrada reciente de Turing en Una Compañía para la Filosofía contiene la siguiente declaración:

Podemos depender de una máquina de Turing que capture las relaciones
funcionales del cerebro”, ya durante mucho tiempo “estas relaciones entre
las entradas y las salidas se encuentran funcionalmente bien-formadas, de
tal forma que pueden ser descrito mediante…relaciones matemáticas… de
tal forma, que sabemos que alguna versión específica de una máquina de
Turing será capaz de representarlas” (Guttenplan).

Searle llegó a una conclusión similar:

¿Es posible simular el comportamiento del cerebro humano mediante una
máquina?

La respuesta parece ser… de manera irrefutable “SI”… Interpretada de manera normal, la pregunta quiere decir:

¿Existe alguna descripción del cerebro que se parezca a la descripción que
podríamos hacer de una simulación computacional de las operaciones del
cerebro?

A partir de la tesis de Church, según la cual cualquier procedimiento que pueda ser simulado (paso por paso) por un computador digital, resulta trivial que la respuesta a la pregunta es claramente afirmativa (Searle 1992:200).

Asimismo, Johnson-Laird y Churchlands expusieron lo siguiente:

Si es posible garantizar que la tesis de Church-Turing es correcta y, además, estamos seguros de que es así entonces:

Si pensamos que el funcionalismo es falso, entonces tendríamos que plantearnos la construcción de una máquina que verificara esto.
Por el contrario, si defendemos el funcionalismo entonces tendríamos que creer que la conciencia, en esencia, es tan sólo un proceso computacional.

La tesis de Church-Turing expone que si el tiempo es computable, entonces se puede computar mediante una máquina de Turing. Asumiendo que es posible computar el cerebro, entonces podemos simular este principio mediante un ordenador (Churchland and Churchland 1983:6).

Como previamente se ha mencionado, Churchaland and Churchland parece creer, erróneamente, que los "resultados hacen referencia… a que un computador digital, sólo muestra los programas correctos, con suficiente tiempo y memoria, puede… mostrar alguna forma sistemática de responder a las etapas" de Turing (1990:26). No existe explicación alguna a cerca de las restricciones de hablar de "patrones sistemáticos" que son efectivamente calculables.

La tesis de Church-Turing no contempla que el cerebro (o la mente, o la consciencia) pueda ser modelada por un programa de una máquina de Turing, sin contradecir la conjetura que cree que el cerebro (o la mente, etc) es científicamente explicable.

Cada uno de los autores citados parecen asumir como la verdad de un cierre de la tesis M, que denominaremos tesis S, cuyo enunciado se muestra a continuación:

"Any process that can be given a mathematical description (or that is scientifically describable or scientifically explicable) can be simulated by a Turing machine."

Como la tesis M, ni la tesis de Church-Turing propiamente llamada ni ningún resultado probado por Turing o Church enlaza con la tesis S. Esto se produce cuando la tesis no se acepta totalmente, cuando se hace referencia al mundo real.

La tesis S toma, como entradas, las sensaciones que percibimos como falsas; las cuales se pueden relacionar fácilmente con la tesis M. Cualquier dispositivo u órgano que procese internamente pueden ser descrito completamente mediante el concepto de funciones efectivamente calculables, por lo que pueden ser simulados perfectamente mediante un programa que se pueda ejecutar en una máquina de Turing (se determina que las salidas de los dispositivos u órganos son Turing-computables). Es decir, también se puede expresar como un número computable, en opinión de Turing); pero cualquier dispositivo u órgano del que podamos obtener una descripción matemática mediante una función que no sea efectivamente calculable no puede ser tampoco simulada.

Como Turing mostró, hay un número infinito de funciones no computables. Los ejemplos de la lógica son las famosas funciones de parada de Turing (descritos en la entrada de la máquina de Turing) y la función D, cuyo dominio se encuadró en las fórmulas bien formadas del cálculo de los predicados y cuyos valores, D(x), son 1 o 0 en función de que X es, o no es, deducible del axioma de los predicados lógicos de Bernays-Hilbert-Ackermann.