Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot Gentileza de Rafael José Rodríguez 1 Preparado por Patricio Barros Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot Reseña Este libro, que es una introducción elemental a la teoría de los algoritmos, está dedicado a la explicación de uno de los conceptos esenciales de las matemáticas, al del algoritmo. En el libro se examinan cuestiones limítrofes de la lógica matemática y la teoría de las máquinas automáticas de tratamiento de la información. Gentileza de Rafael José Rodríguez 2 Preparado por Patricio Barros Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot Índice Prefacio Introducción § 1. Algoritmos numéricos § 2. Algoritmos para la resolución de problemas lógicos § 3. El problema de las palabras § 4. Máquina de calcular con mando automático § 5. Programas (los algoritmos de máquina) § 6. La necesidad de precisar el concepto de algoritmo § 7. La máquina de Turing § 8. Realización de algoritmos en la máquina de Turing § 9. Hipótesis básica de la teoría de los algoritmos § 10. La máquina universal de Turing § 11. Problemas algorítmicamente insolubles Observaciones finales Gentileza de Rafael José Rodríguez 3 Preparado por Patricio Barros Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot Este libro, que es una introducción elemental a la teoría de los algoritmos, está dedicado a la explicación de uno de los conceptos esenciales de las matemáticas, al del algoritmo. En el libro se examinan cuestiones limítrofes de la lógica matemática y la teoría de las máquinas automáticas de tratamiento de la información. El libro fue escrito a base de las conferencias de divulgación y los informes generales que dio el autor en la ciudad de Penza desde el año 1951 ante diferentes auditorios y del artículo del mismo nombre publicado en la revista "Математиа в школе" («Las matemáticas en la escuela») (Nos 4 y 5, 1956). A aquellos que deseen estudiar con más profundidad estas cuestiones se les puede recomendar el libro de Boris Avraamovich Trajtenbrot: "Алгоритмы Автоматные и вычислительной техники, редакционная soviétskoye Радио Так что, Москва, 1974", «Los algoritmos y los autómatas de cómputo, editorial Soviétskoye Radio, Moscú, 1974). Gentileza de Rafael José Rodríguez 4 Preparado por Patricio Barros Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot Introducción En los años de postguerra las computadoras de alta velocidad han tenido un considerable desarrollo. Hoy en día se emplean para la resolución de los más variados problemas matemáticos y lógicos. La característica peculiar de estas computadoras, la que las distingue de las máquinas de calcular anteriores, consiste en que, al cumplir sus funciones, ellas, desde el momento en que se introducen los datos iniciales y el programa hasta que se imprime el resultado final, trabajan sin ninguna intervención del hombre. La productividad de las computadoras electrónicas modernas es enorme: ellas realizan cientos de miles de operaciones aritméticas en un segundo, lo que es por lo menos 100 veces más de lo que puede hacer en un solo turno un empleado de alta calificación que trabaje con un buen aritmómetro de teclas1. La esfera del empleo de las computadoras automáticas continúa ampliándose: las máquinas resuelven complejos sistemas de ecuaciones, traducen de una lengua a otra, juegan al ajedrez, etc. Las perspectivas del empleo de las computadoras automáticas en la industria son enormes, ellas pueden realizar el control de todos los procesos tecnológicos en grandes fábricas. Además, la posibilidad de un rápido y seguro tratamiento de la información y también de un análisis de datos experimentales crea la premisa para que aparezcan métodos nuevos de investigación que antes no estaban al alcance en muchas ramas de la ciencia. Hoy, ya está completamente reconocido que las computadoras automáticas son un potente instrumento del trabajo intelectual, capaces no sólo de aligerar al hombre de este trabajo, sino de liberarlo por completo de algunas clases de un grande y tenso trabajo mental. Al mismo tiempo los éxitos conseguidos pueden crear y crean muchas injustificadas ilusiones y pronósticos puramente fantásticos sobre la omnipotencia de estas máquinas. Particularmente se debe indicar el alboroto de propaganda que se ha levantado en parte de la prensa extranjera sobre «el cerebro gigante electrónico», sobre los autómatas capaces de resolver cualquier problema y reemplazar el trabajo creador del científico. 1 Desde el punto de vista de la ejecución de operaciones de cómputo. Gentileza de Rafael José Rodríguez 5 Preparado por Patricio Barros Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot Adquiere una gran actualidad y agudeza, en relación con las circunstancias indicadas, la cuestión sobre las clases del trabajo intelectual que pueden cumplir las computadoras automáticas. Desde un determinado punto de vista esta cuestión se examina y soluciona en la moderna teoría de los algoritmos que es una rama importante de la lógica matemática. Es característico para la lógica matemática el estudio de la esencia de tales nociones como «proceso de cómputo», «demostración matemática», «algoritmo», etc. Ya varios años antes de la creación de las computadoras automáticas electrónicas modernas en la lógica matemática fue elaborada un concepto exacto de «algoritmo» y un esquema general de una computadora automática (la máquina de Turing), también se aclaró la estrecha relación que existe entre los algoritmos y las máquinas. Eso permitió resolver una serie de importantes teoremas que daban luz a la esencia de los procesos que se realizan en las computadoras automáticas; en particular, fue rigurosamente demostrada la existencia de tales problemas para los cuales es imposible su resolución en máquina. El presente libro está dedicado al estudio de la relación entre los algoritmos y las máquinas. En los §1 al §3 se explica en una serie de ejemplos lo que es algoritmo y se componen los algoritmos de resolución de problemas matemáticos y lógicos de varias clases. En los §4 y §5 se exponen los principios de construcción de las máquinas computadoras electrónicas y de composición de programas o sean los algoritmos adaptados para su realización en máquinas. Los epígrafes 6 al 11 están dedicados a una serie de importantes casos de la teoría de los algoritmos. En calidad del concepto básico de la teoría ha sido aceptado el concepto de la máquina de Turing. Muchas demostraciones son tan voluminosas que no permiten darlas por entero en un libro tan pequeño. Por eso, aquí hay ciertas divergencias de la rigurosidad y de la plenitud de la exposición las que, sin embargo nos parece, no sólo no molestan, sino que, al revés, favorecen a la mejor comprensión de la esencia de la cosa. Para generalizar el cuadro sobre el tema, en el §6 se reúnen en un resumen algunas cuestiones. Gentileza de Rafael José Rodríguez 6 Preparado por Patricio Barros Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot Hagamos una observación más. Se llaman electrónicas a las computadoras modernas de mando automático, puesto que sus partes principales están construidas con elementos electrónicos. El empleo de la técnica electrónica asegura un gran ahorro de tiempo necesario para realizar las operaciones que cumple la máquina. Sin embargo, la particularidad fundamental de estas máquinas, el control automático de los procesos que tienen lugar en ellas, no es precisamente el empleo de la técnica electrónica. Los elementos electrónicos, en un principio, podrían ser reemplazados incluso por mecanismos, o sea, podría crearse una máquina computadora mecánica de control automático capaz de resolver los mismos problemas que la electrónica (pero, claro, mucho más despacio). Así que no se puede concebir que la aparición de las computadoras de esta nueva clase es el resultado del desarrollo solamente de la técnica electrónica. Es más, la primera descripción de una máquina computadora automática (la máquina de Turing, véase el §7) se dio en la teoría de los algoritmos ya en el año 1936 y se presentó como la descripción de un mecanismo. Las primeras máquinas construidas (1940) fueron electromecánicas. En el presente libro al describir la construcción de las computadoras no nos concentraremos en los detalles técnicos, fundamentalmente prestaremos la atención al estudio de los principios de interacción de las diferentes partes de la computadora. Este enfoque corresponde al principal fin del libro que consiste en revelar las posibilidades matemáticas y lógicas de las computadoras y no en mostrar el aspecto técnico de la cosa. Gentileza de Rafael José Rodríguez 7 Preparado por Patricio Barros Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot §1. Algoritmos numéricos El concepto de algoritmo pertenece a las nociones fundamentales de la matemática. Entendemos por algoritmo la prescripción exacta sobre el cumplimiento de cierto sistema de operaciones en un orden determinado para la resolución de todos los problemas de algún tipo dado. Se sobrentiende que la frase anterior no es la definición matemática exacta del concepto de algoritmo, esta frase más bien explica el sentido de la palabra «algoritmo» aclarando su significado. A pesar de todo esta explicación es comprensible y clara a cada matemático; ella refleja la concepción de algoritmo que espontáneamente se ha formado y empleado en la matemática desde los tiempos antiguos. Los algoritmos más sencillos son las reglas con las que se cumplen una u otra de las cuatro operaciones aritméticas en el sistema de numeración decimal (el propio término de algoritmo procede del nombre del matemático uzbeko Al - Jwarizmi quien ya en el siglo IX propuso tales reglas). Por ejemplo, la acción de la suma de dos números de varias cifras se descompone en una cadena de operaciones elementales en las que, al realizar cada una de ellas, la persona que hace la cuenta trata solamente con dos cifras de los respectivos sumandos (una de ellas puede tener una marca que indica el traslado de una unidad). Estas operaciones son de dos tipos: 1. anotación de la cifra correspondiente de la suma, 2. marca sobre el traslado por encima de la cifra vecina de la izquierda; aquí la regla prescribe un orden determinado del cumplimiento de estas operaciones (de derecha a izquierda). El carácter formal de estas operaciones elementales consiste en que ellas pueden ser realizadas automáticamente con una tabla de suma de cifras dada una vez para siempre, abstrayéndose por completo del sentido de su contenido. Con las otras tres operaciones aritméticas la cosa está en forma análoga, lo mismo pasa con el cálculo de la raíz cuadrada y con otras. El carácter formal de las respectivas prescripciones (algoritmos) parece ser que no crea ninguna duda (eso sobre todo se observa cuando los escolares aprenden las reglas para extraer la raíz Gentileza de Rafael José Rodríguez 8 Preparado por Patricio Barros Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot cuadrada). Veamos en calidad de ejemplo el algoritmo de Euclides que resuelve todos los problemas del tipo siguiente: Hallar el máximo común divisor de dos números naturales dados a y b. Es evidente que existen tantos diferentes problemas de este tipo como diferentes pares de números a y b. Es sabido que la solución de cualquier problema de éstos se puede obtener mediante la composición de una sucesión disminuyente de números de los que el primero será el mayor de los dos dados, el segundo, el menor, el tercero será el resto de la división del primero por el segundo, el cuarto será el resto de la división del segundo por el tercero, etc., basta que no se haga la división sin resto. El divisor de esta última división será el resultado que se busca. La división se puede reducir a una sustracción repetida. Basándose en esto se podría presentar una prescripción válida para la resolución de cualquiera de estos problemas en forma de la siguiente sucesión de indicaciones: Indicación 1. Examina los dos números oyó. Pasa a la indicación siguiente. Indicación 2. Compara los dos números (a = b, o a < b, a > b); pasa a la indicación siguiente. Indicación 3. Si los números examinados son iguales, cada uno de ellos da el resultado que se busca. El proceso de cómputo se para. Si no es así, pasa a la siguiente indicación. Indicación 4. Si el primero de los números examinados es menor que el segundo, cámbialos de lugar y continúa su examen. Pasa a la siguiente indicación. Indicación 5. Resta el segundo de los números examinados del primero y examina dos números: el sustraendo y el resto. Pasa a la indicación 2. Después de que las cinco indicaciones se hayan cumplido hay que volver de nuevo a la segunda, pasar a la tercera, a la cuarta, a la quinta, y otra vez a la segunda, a la tercera, etc., basta que se obtengan números iguales, o sea, basta que se cumpla la condición que se contiene en la tercera indicación; entonces se cesa el proceso. Es verdad que en la matemática los algoritmos no siempre se expresan de una manera tan formalista; no obstante, a nadie le vendrán dudas sobre la posibilidad Gentileza de Rafael José Rodríguez 9 Preparado por Patricio Barros Los algoritmos y la resolucion automática de problemas Boris Avraamovich Trajtenbrot de presentar de tal manera formal cualquiera de los algoritmos conocidos. En la descripción anterior del algoritmo de Euclides figuran en calidad de operaciones elementales en las que se descompone el proceso de resolución del problema, la sustracción de dos números, la comparación de dos números y el cambio de lugar de dos números. Ahora bien, se puede fácilmente notar que esta descomposición puede ser considerablemente desarrollada. Por ejemplo, la misma indicación 5 sobre la sustracción de los dos números examinados puede ser desenvuelta en un sistema de indicaciones que describan el algoritmo de sustracción de dos números. Sin embargo, a causa de su gran sencillez y de la costumbre a las reglas de las operaciones aritméticas, en casos similares no se continúa detallando el algoritmo. Los algoritmos, en concordancia con los cuales la resolución de los problemas planteados se reduce al empleo de las cuatro operaciones aritméticas, se llaman algoritmos numéricos. Estos juegan un gran papel en los más variados terrenos tanto de la matemática elemental como de la superior y se presentan corrientemente en forma de prescripciones textuales o de diferentes fórmulas y esquemas. Por ejemplo, el algoritmo de la resolución de un sistema de dos ecuaciones de primer grado con dos incógnitas: se da con las fórmulas en las que están completamente expresados tanto la composición de las operaciones como el orden de su ejecución. En las fórmulas anteriores se prevé una misma cadena de operaciones para todos los problemas del tipo dado (o sea, con Gentileza de Rafael José Rodríguez 10 Preparado por Patricio Barros