La Mente Del Emperador Capitulo 2

LA MENTE NUEVA DEL EMPERADOR

ALGORITMOS Y MÁQUINAS DE TURING FUNDAMENTOS DEL CONCEPTO DE ALGORITMO

En la aparición del libro de Al- Khowârizm ya se conocían ejemplos de algoritmos. Uno de los más familiares, que data de la época griega antigua (c. 300 a.C.), es el procedimiento hoy conocido como algoritmo de Euclides para encontrar el máximo común divisor de dos números un ejemplo de como nos ayudará considerar un par concreto de números, por ejemplo 1365 y 3654. El máximo común divisor es el mayor número entero que es divisor exacto de ambos. Para aplicar el algoritmo de Euclides dividimos uno de los dos números por el otro y tomamos el resto: 3654 entre 1365 cabe a 2 y restan 924 (3654 - 2730). Ahora reemplazamos nuestros números originales por el resto, a saber 924, y el divisor de la operación anterior a saber 1365. Repetimos la operación utilizando ahora este nuevo par de números: 1365 dividido entre 924 cabe a 1 y restan 441.

Esto nos da un nuevo par, 441 y 924, y entonces dividimos 924 entre 441 obteniendo el resto 42 (924 - 882), y así sucesivamente hasta llegar a una división exacta. Escrito en orden todo esto tenemos

3654 : 1365 da resto 924 1365 : 924 da resto 441 924 : 441 da resto 42 441 : 42 da resto 21 42 : 21 da resto 0

El último número por el que dividimos, es decir 21, es el máximo común divisor buscado.

El algoritmo de Euclides es el procedimiento sistemático mediante el cual encontramos este divisor. Hemos aplicado este procedimiento a un par de números particular, pero el procedimiento se aplica a cualquier par de números de cualquier magnitud. Para números muy grandes el procedimiento puede tardar mucho tiempo, y cuanto mayores sean los números más tiempo necesitará. Pero en cualquier caso el procedimiento llegará al final y se obtendrá una respuesta definida en un número finito de pasos. En cada paso está perfectamente claro qué operación debe realizarse, y también es perfectamente clara la decisión de cuándo debe darse por terminado todo el proceso. Además, la descripción del proceso total puede presentarse en términos finitos, a pesar de que se aplique a números naturales de tamaño ilimitado. (Los "números naturales" son simplemente los números enteros no negativos1 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11...). De hecho, es fácil construir un "organigrama" (finito) para describir la operación lógica completa del algoritmo de Euclides

Parece claro que también Turing consideraba el cerebro humano como una "máquina" en este sentido, de modo que cualquiera que fuera la actividad que pudiera llevar a cabo un matemático cuando aborda sus problemas, ésta también tendría que entrar en la etiqueta de "procedimientos mecánicos".

Aunque esta visión del pensamiento humano parece haber sido valiosa para Turing a la hora de desarrollar este concepto capital, no estamos obligados ni mucho menos a adherirnos a ella. En realidad, al precisar lo que se debía entender por procedimiento mecánico, Turing mostró que existen algunas operaciones matemáticas perfectamente bien definidas que no pueden ser llamadas mecánicas en ningún sentido. Hay quizá cierta ironía en el hecho de que este aspecto de la obra de Turing puede hoy proporcionarnos indirectamente argumentos contra su propio punto de vista respecto a la naturaleza de los fenómenos mentales. Sin embargo, esto no nos interesa por el momento. Primero necesitamos descubrir cuál es realmente el concepto que tiene Turing de un procedimiento mecánico.

EL CONCEPTO DE TURING

Tratemos de imaginar un dispositivo para llevar a cabo un procedimiento de cálculo permitirnos idealizar un poco en una máquina matemáticamente idealizada. Queremos que nuestro dispositivo tenga un conjunto discreto de posibles estados diferentes, en número finito Los llamaremos estados internos del dispositivo. Sin embargo no queremos limitar el tamaño de los cálculos que nuestro dispositivo pueda realizar. Recordemos el algoritmo de Euclides descrito anteriormente; no hay límite para la magnitud de los números sobre los que el algoritmo puede actuar. El algoritmo o el procedímiento general de cálculo es el mismo independientemente de la magnitud de los números. Para números muy grandes el procedimiento puede durar mucho tiempo y necesitar una gran cantidad de papel donde realizar las operaciones, pero el algoritmo será el mismo conjunto finito de instrucciones.

Así, aunque tenga un número finito de estados internos, nuestro dispositivo debe poder manejar un input de cualquier tamaño. Además, el dispositivo dispondrá de un espacio ilimitado de almacenamiento externo para sus cálculos, y podrá también producir un output de tamaño ilimitado. Puesto que nuestro dispositivo tiene sólo un número finito de estados internos distintos no cabe esperar "cargar" todos los datos externos ni todos los resultados de sus propios cálculos.

CODIFICACIÓN BINARIA DE LOS DATOS NUMÉRICOS

El sistema unario es muy poco eficiente para la representación de números de gran tamaño. En consecuencia, utilizaremos normalmente el sistema binario de numeración que describimos anteriormente. No obstante, no podemos hacer esto de forma directa, leyendo sencillamente la cinta como un número binario. Tal como están las cosas no habría modo de definir cuándo termina la representación binaria del número y comienza la sucesión infinita de 0's que representa la cinta en blanco hacia la derecha. Necesitamos alguna notación para dar por terminada la descripción binaria de un número. Más aún, a menudo tendremos que introducir varios números, como el par de números que requiere el algoritmo de Euclides.

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.

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.

NÚMEROS DIFERENTES DE LOS NATURALES

consideramos

...