Algoritmos y la resolucion automatica

Instituto Tecnológico de La Paz
Secretaría de Educación Pública



Colección de textos para los cursos de Pepe Farah



Los algoritmos y la resolución automática de problemas



B. A. Trajtenbrot



2 0 0 2

L a P a z B a j a C a l i f o r n i a S u r
Los algoritmos y la resolución automática de problemas

B. A. Trajtenbrot

Í n d i c e


Prefacio
3

Introducción
3
§1.
Algoritmos numéricos
5
§ 2.
Algoritmos para la resolución de problemas lógicos
9
§ 3.
El problema de las palabras
18
§ 4.
Máquina de calcular con mando automático
29
§ 5.
Programas (los algoritmos de máquina)
34
§ 6.
La necesidad de precisar el concepto de algoritmo
41
§ 7.
La máquina de Turing
47
§ 8.
Realización de algoritmos en la máquina de Turing
53
§ 9.
Hipótesis básica de lateoría de los algoritmos
68
§ 10.
La máquina universal de Turing
71
§ 11.
Problemas algorítmicamente insolubles
76

Observaciones finales
79



Prefacio
Este libro, que es una introducción a la teoría de los algoritmos, esta dedicado a la explicación de uno de los conceptos esenciales de la matemática, al del algoritmo. En el libro se examinan cuestiones limítrofes de la lógica matemática y la teoríade 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 dió el autor en la ciudad de Penza desde el año de 1951 ante diferentes auditorios y del artículo del mismo nombre publicado en la revista “La matemática en la escuela”, números 4 y 5 en el año 1956.
A aquellos que deseen estudiar con masprofundidad estas cuestiones se les puede recomendar el libro: Los algoritmos y los autómatas de computo, de B. A. Trajtenbrot, editorial Radio soviética, Moscú, 1974).

Introducción
En los años de posguerra las computadoras de alta velocidad han tenido un considerable desarrollo. Hoy en día se emplean para la solución de los más variados problemas matemáticos y lógicos. La característica peculiar deestas computadoras, la que 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 operacionesaritméticas en un segundo, lo que es por lo menos 100 veces más de lo que puede hacer en un sólo turno un empleado de alta calificación que trabaje con un buen aritmómetro de teclas. (Desde el punto de vista de la ejecución de operaciones de computo)
La esfera del empleado de las computadoras automáticas continúa aplicándose: las máquinas resuelven complejos, sistemas de ecuaciones, traducen deuna lengua a otra, juegan al ajedrez, etcétera 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 deinvestigación que antes no estaban al alcance en muchas ramas de la ciencia.
Hoy, ya esta completamente reconocido que las computadoras automáticas son un potente instrumento del trabajo intelectual, capaces no solo de aligerar al hombre de este trabajo, sino de liberarlo por completo de algunas clases de un gran y tenso trabajo mental.
Al mismo tiempo los éxitos conseguidos pueden crear y creanmuchas 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 revolver cualquier problema y reemplazar el trabajo creador del científico.
Adquiere una gran actitud y...