Gödel y Turing (Parte 5)

(A la parte 4 - A la parte 6)

Más sobre la tesis de Turing

“El trabajo de Turing en la construcción de tablas de comportamiento parece inmerso en la cuestión de la programación de computadoras, tanto más cuanto Turing utilizó una notación abreviada equivalente a la definición de subrutinas. Aunque no puede decirse que la idea de la programación tenga su origen en el trabajo de Turing, la verdad es que en éste la idea es formalizada de tal modo que es difícil creer que las computadoras todavía no existieran. Sin embargo, un asunto tiene que enfatizarse: en su trabajo Turing no estaba considerando las máquinas de computación (que llegarían sólo diez años más tarde), lo que Turing hacia era modelar la acción de la mente humana.”
(HODGES, Andrew – Turing – Editorial Norma, Bogotá, 1998. )

Un algoritmo es, informalmente hablando, un procedimiento mecánico (o una receta) para resolver un problema determinado. Específicamente serán de nuestro interés los problemas matemáticos que involucran números enteros positivos.

Normalmente un algoritmo se expresa como una serie de instrucciones que deben seguirse paso a paso al pie de la letra (de la misma manera en que una computadora ejecuta los pasos de un programa). Supongamos, por ejemplo, que nuestro problema consiste en calcular la parte entera de la raíz cuadrada de un número dado. Como primer intento podríamos plantear sencillamente el “algoritmo” siguiente:

Propuesta I:

Entrada: n.
Paso 1: Calcule la parte entera de la raíz cuadrada de n y llámela k.
Salida: k.

Sin embargo, como es fácil imaginar, las instrucciones que acabamos de escribir no constituyen genuinamente un algoritmo. La instrucción principal dice sencillamente “resuelva el problema”, sin indicarnos realmente el modo de hacerlo.

Para que un conjunto de instrucciones constituya verdaderamente un algoritmo deberíamos estar seguros de que cada uno de sus pasos puede ser ejecutado mecánicamente, mientras que en la Propuesta I no tenemos ninguna garantía de que el Paso 1 cumpla esa condición. El siguiente conjunto de instrucciones nos da una respuesta mejor para nuestro problema:

Propuesta II:

Entrada: n.
Paso 1: Asigne a la variable k el valor 1.
Paso 2: Eleve k al cuadrado.
Paso 3: Si el cuadrado de k es menor o igual que n, sume 1 al valor de k y vaya al paso 2.
Paso 4: Si el cuadrado de k es mayor que n, vaya al paso 5.
Paso 5: Reste 1 al valor de k.
Salida: k.

Por ejemplo, si n = 22, las instrucciones nos llevan a calcular los cuadrados de 1, 2, 3,... Estos cálculos llegarán hasta el cuadrado de 5, que es el primer número que es excede a 22. La salida es k = 4, la respuesta correcta del problema.

La Propuesta II es un refinamiento de la Propuesta I, pues está construida subdividiendo cada instrucción de ésta en pasos más sencillos. Pero ¿es cierto que cada paso del segundo algoritmo puede realizarse mecánicamente? Analicemos: cada instrucción de la Propuesta II nos pide, o bien elevar un número al cuadrado, o bien sumarle o restarle una unidad, o bien comparar dos números enteros. Nuestra familiaridad con calculadoras y computadoras nos indica que, en efecto, todas estas operaciones pueden efectuarse mecánicamente.

Pero, si no contásemos con esa familiaridad ¿cómo podríamos tener la absoluta certeza de que existe un procedimiento mecánico para, por ejemplo, elevar un número al cuadrado? El modo de lograr esta certeza sería refinar una y otra vez la Propuesta II hasta lograr un conjunto de instrucciones tan sencillas que no quepa ninguna duda de que pueden ser ejecutadas mecánicamente. La idea central de la Tesis de Turing es que el último refinamiento de cualquier algoritmo será, a la larga, una máquina de Turing (o máquina T, para abreviar).

En el artículo donde presenta por primera vez su tesis (1), Turing ofrece el siguiente argumento como justificación de la misma (2):

Turing analiza los pasos que sigue una persona al realizar un cálculo matemático. Dice que en esa tarea, los humanos revisamos cifra por cifra los números involucrados en el cálculo y que en cada paso elemental (o irreducible) del mismo escribimos o borramos un símbolo. Finalmente argumenta que nuestro modo de proceder está siempre regido por nuestro “estado mental” en cada instante (análogo al “estado interno” de una máquina T). Por lo tanto, dice Turing, los pasos elementales de cualquier cómputo son equivalentes a los que realiza una máquina T.

Es interesante observar que en su razonamiento Turing analiza los pasos que sigue una persona (no un artefacto) al realizar un cálculo. Por lo tanto, al definir su máquina, Turing estaba intentando dar un modelo matemático del funcionamiento del cerebro humano. En otras palabras, al momento de escribir su artículo, Turing consideraba que el cerebro humano funciona esencialmente igual que computadora. La complejidad del cerebro es, desde luego, mucho mayor que el de cualquier computadora actual, pero la diferencia entre ambos residiría sólo en una cuestión de complejidad, no en una cuestión de naturaleza esencial.

En escritos posteriores Turing modificó esta primera convicción y pasó a creer que el cerebro humano tiene en realidad capacidades que son imposibles de alcanzar por una computadora, ni siquiera en teoría (3). Concretamente, en esta segunda etapa de su pensamiento, Turing creía que los presentimientos o la intuición marcaban una diferencia real entre mente humana y la computadora mecánica.

¿Es el cerebro humano una computadora (extraordinariamente compleja, pero computadora al fin) o, por el contrario, existe una diferencia esencial entre “computadora” y “cerebro”? No existe por el momento (y tal vez nunca exista) un acuerdo unánime acerca del cuál es la respuesta a esta pregunta. En la actualidad, sólo por citar algunos ejemplos, el físico-matemático Roger Penrose es defensor de la convicción según la cual el cerebro es esencialmente superior a una computadora y que no pueden equipararse, ni siquiera en teoría. Por el contrario, el filósofo Daniel Dennett y el matemático Douglas Hofstadter sostienen la idea opuesta, es decir, que el cerebro es fundamentalmente una computadora muy compleja y que es posible, al menos en teoría, que en el futuro lejano las computadoras artificiales lleguen a equipararse al cerebro humano en sus capacidades. El autor de estas notas debe decir que simpatiza con esta última postura. [...]

Notas:

(1) On computable numbers with an aplication to the Entscheidungsproblem, publicado en el Proceedings of London Mathematical Society, vol. 42 (1937), pp. 230 – 265.

(2) Decíamos en la nota anterior que la Tesis de Turing no puede ser demostrada matemáticamente. Por lo tanto, cualquier argumento que intente justificarla debe ser necesariamente de carácter extra-matemático.

(3) La pregunta de si las máquinas pueden pensar preocupó a Turing durante décadas. En 1950, por ejemplo, presentó la idea de un test (hoy conocido como Test de Turing) que permitiría en teoría determinar si una computadora piensa o no. La idea del test es que si ante preguntas de carácter general una computadora puede dar respuestas que no se distingan de las que daría una persona, entonces puede decirse que la máquina efectivamente piensa. Desde su misma formulación el test ha sido motivo de mucha controversia.

(A la parte 4 - A la parte 6)