Instrucciones detalladas que definen un proceso computacional (que se dice entonces que es algorítmico), que comienza con una entrada arbitraria (de un cierto número de entradas que son posibles para el algoritmo dado), y con instrucciones destinadas a obtener un resultado (o salida) que está totalmente determinado por la entrada. Por ejemplo, las reglas que se enseñan en las escuelas primarias para sumar, restar, multiplicar y dividir en columnas son algoritmos; en estos algoritmos los posibles resultados son números enteros no negativos escritos en el sistema decimal, mientras que las posibles entradas son pares ordenados de dichos números. En general, no se supone que el resultado se obtenga necesariamente: el proceso de aplicación de un algoritmo a alguna entrada posible (es decir, un proceso algorítmico que procede a partir de esta entrada) también puede terminar sin que se obtenga un resultado (en tal caso se tiene una parada sin resultado) o puede no terminar en absoluto. Si el proceso termina (no termina), entonces se dice que la entrada es adecuada (no es adecuada) para el algoritmo en cuestión.
Un resultado importante en esta área es la indecidibilidad del llamado problema de parada. Es posible construir un algoritmo $ \alpha $de tal manera que no haya un algoritmo que decida si alguna entrada arbitraria que es posible para $ \alpha $es también adecuada para $ \alpha $. En particular, se puede encontrar un algoritmo $ \alpha $para el que el conjunto de sus posibles entradas es el conjunto de los números naturales.
La noción de algoritmo es uno de los conceptos centrales en las matemáticas modernas, especialmente en el área de los cálculos. A continuación se ofrece un ejemplo. Encontrar la solución numérica de ecuaciones de un tipo dado equivale a construir un algoritmo que convierta una ecuación arbitraria de este tipo y un número racional positivo arbitrario $ \epsilon $ en un número (o un conjunto de números) que difiera de la(s) raíz(es) de esta ecuación en menos de $ \epsilon $. Sin embargo, el término «proceso de cálculo», tal como se utiliza en el contexto de un algoritmo, no debe entenderse como meros cálculos numéricos: incluso en el álgebra elemental se utilizan cálculos con letras. Los cálculos aritméticos estándar incluyen algunos símbolos que no son números (paréntesis, signos de igualdad, símbolos de operadores aritméticos). Por lo tanto, es conveniente considerar los algoritmos que implican símbolos arbitrarios y objetos compuestos por símbolos. El ejemplo más sencillo de este tipo de objetos es una secuencia lineal de símbolos que forman una palabra. También es posible considerar objetos «no lineales»: matrices algebraicas, árboles de derivación de algún lenguaje formal y grafos generales. Intuitivamente, el menor requisito para las entradas y los resultados de los algoritmos es que sean objetos constructivos (véase Objeto constructivo). Así, el concepto de algoritmo es muy general. Se puede hablar de un algoritmo para la traducción de un lenguaje a otro, de un algoritmo de un controlador aéreo (que procesa la información sobre los movimientos de los aviones según unas reglas fijas), y de otros ejemplos de procesos de control descritos algorítmicamente. En consecuencia, el concepto de algoritmo es una de las ideas centrales de la cibernética y la informática.
Ejemplo de un algoritmo.
Serán las posibles entradas y los posibles resultados todas las palabras posibles sobre el alfabeto $ \{ a, b \} $. La transición de una palabra $ X $ a una palabra $ Y $ es «permisible» en los dos casos siguientes (donde $ P $denota una palabra arbitraria): 1) $ X $ es de la forma $ aP $, y $ Y $ es de la forma $ Pb $; o 2) $ X $ es de la forma $ baP $, mientras que $ Y $ es de la forma $ Paba $. Las instrucciones se formulan como sigue: «designando alguna palabra como entrada, ejecutar las transiciones permitidas hasta obtener una palabra de la forma aaP; entonces detenerse y dejar que la palabra P sea el resultado» . Estas instrucciones constituyen un algoritmo, que será denotado por $ \mathfrak A $. Tome la palabra $ babaa $como entrada. Después de una transición se obtiene $ baaaba $; después de la segunda, se obtiene $ aabaaba $. Aquí el algoritmo se detiene con $ baaba $ como resultado. Considere otra entrada $ baaba $. Se obtiene, sucesivamente, $ abaaba, baabab, abababa, bababab, babababa , . . . Se puede demostrar que este proceso nunca terminará (es decir, ninguna de las palabras generadas comenzará nunca con $ aa $). Ahora tome $ abaab $como entrada. Se obtiene $ baabb, abbaba, bbabab $; no son posibles más transiciones permisibles y, al mismo tiempo, no se satisface la condición de terminación. Se tiene una parada sin resultado. Así, la entrada $ babaa $ es adecuada para $ \mathfrak A $, y las entradas $ baaba $ y $ abaab $ no lo son.
El significado de los algoritmos.
En la ciencia, los algoritmos se encuentran en todas partes: una solución «general» a un problema requiere un algoritmo. La capacidad del hombre para sumar números es un ejemplo de ello. No el hecho de que pueda encontrar, tarde o temprano, la suma de dos números cualesquiera, sino en el sentido de que posee un método para la suma única de dos números cualesquiera dados en forma escrita, es decir, un algoritmo de suma como el conocido método de suma por columnas. «Generalmente» la resolución de un problema se formaliza como la resolución de un problema algorítmico. Un problema algorítmico se compone de instancias de problemas separados, y es necesario encontrar un único algoritmo para la solución de todos ellos. Si no existe tal algoritmo, se dice que el problema algorítmico es irresoluble. Así, el problema de la resolución numérica de ecuaciones de un tipo determinado y el problema de la traducción automática son problemas algorítmicos. Sus instancias de problemas son, respectivamente, encontrar la solución numérica de ecuaciones individuales del tipo dado, y la traducción de frases individuales. Otros ejemplos son la verificación de igualdades algebraicas en álgebra; el problema algorítmico del reconocimiento de la deducibilidad de proposiciones a partir de axiomas dados en lógica matemática. (En la lógica matemática el concepto de algoritmo también es importante, ya que sirve de base al concepto clave de cálculo, que es una generalización y una forma más precisa de los conceptos intuitivos de «prueba» y «demostración»). El establecimiento de la irresolubilidad de un problema algorítmico dado (por ejemplo, el problema de establecer la verdad o demostrabilidad de oraciones en algún lenguaje lógico-matemático) es importante, porque muestra que, en principio, las instancias específicas de ese problema sólo pueden ser resueltas por métodos que son específicos para cada instancia individual del problema.
La importancia científica del concepto de algoritmo ha sido reconocida desde hace mucho tiempo. Desde los primeros tiempos, se han buscado métodos constructivos para resolver problemas matemáticos. Estos esfuerzos suelen beneficiarse de la nueva disponibilidad de notaciones simbólicas adecuadas. Este proceso ha supuesto una importante contribución al conocimiento científico, sobre todo después de que quedara claro que algunos problemas son intrínsecamente irresolubles (la cuadratura del círculo, etc.). Después de que se reconociera que ciertos problemas no pueden resolverse mediante cálculos directos, en el siglo XIX nació el concepto teórico de conjunto. Sólo después de un período de rápido desarrollo de este concepto (que no implicaba problemas de métodos constructivos en su sentido moderno), fue posible a mediados del siglo XX volver a los problemas constructivos, pero esto se hizo en un nivel diferente, enriquecido por el concepto de algoritmo que había cristalizado entretanto. Este concepto constituye la base de la tendencia constructiva en matemáticas.
La palabra «algoritmo» proviene de la palabra «algoritmi» , siendo esta última la transliteración latina del nombre del matemático árabe del siglo IX Al-Khwarizmi. Un «algoritmo» en la Europa de la Edad Media era «el sistema decimal-posicional y el arte de calcular con él» , ya que es a través de la traducción al latín (siglo XII) del tratado de Al-Khwarizmi que se introdujo el sistema posicional en Europa.
La estructura de un proceso algorítmico.
Un proceso algorítmico es un proceso de conversión consecutiva de objetos constructivos por «pasos» discretos , cada paso consiste en la sustitución de un objeto constructivo por otro. Así, al aplicar el algoritmo $ \mathfrak A $ a la palabra $ baaba $, se suceden las palabras $ baaba, abaaba, baabab $, etc. Si se aplica, por ejemplo, el algoritmo de la resta por columnas al par de números <307, 49 >, se obtienen, sucesivamente, los siguientes objetos constructivos:
$$ \begin{array}{rrrr}307 &3 \7 &punto{0} 7 &punto{3} \dot{0} 7 &\dot{3} \7. &Subrayado – 49 } &subrayado{- 49} &Subrayado – 49 } \\{} & 8 &58 &258 \\\\N-end{array}$$
Se observará que, en una serie de objetos constructivos sucesivos, cada objeto constructivo sucesivo está totalmente determinado (en el marco del algoritmo dado) por el objeto constructivo inmediatamente anterior. En el enfoque más riguroso, se supone también que la transición de cualquier objeto constructivo al inmediatamente posterior es suficientemente «elemental» -en el sentido de que la transformación de un paso del objeto precedente en el inmediatamente posterior es local (no es todo el objeto constructivo el que se transforma, sino sólo su parte limitada por el algoritmo; además, esta transformación misma no está determinada por el objeto precedente completo, sino sólo por una parte limitada del mismo).
En consecuencia, se tiene no sólo un conjunto de entradas posibles y un conjunto de resultados posibles, sino también un conjunto de resultados intermedios posibles, que representan el medio de trabajo en el que evoluciona el proceso algorítmico. En lo que respecta a $ \mathfrak A $, estos tres conjuntos coinciden, pero esto no es cierto para el algoritmo de la resta por columnas – las posibles entradas son pares de números, los posibles resultados son números (todos en el sistema decimal), mientras que los posibles resultados intermedios son registros «de tres pisos» del tipo
$$ \begin{array}{r} p \\\\\a}subrayado{- q } \\\\ r \\\\\N-fin{array}$$
donde $ q $ es el registro escrito del número en el sistema decimal, $ r $ es un registro similar o la palabra vacía, mientras que $ p $ es el registro escrito de un número en el sistema decimal, con puntos sobre algunos de los dígitos. Como regla, se pueden distinguir varios parámetros (no independientes) característicos de un algoritmo: 1) el conjunto de entradas posibles; 2) el conjunto de resultados posibles; 3) el conjunto de resultados intermedios posibles; 4) la regla de inicio; 5) la regla de transición directa; 6) la regla de terminación; y 7) la regla de recuperación del resultado.
Formalización del concepto de algoritmo.
El concepto de algoritmo en su forma general es un concepto matemático fundamental que no puede ser definido en términos de conceptos más simples. En sentido estricto, las formalizaciones del concepto de algoritmo lo restringen en cierto modo. En cada una de estas formalizaciones se da una definición exacta de alguna clase dentro de la cual puede variar cada uno de los parámetros. Las distintas formalizaciones se diferencian entre sí por la selección de dichas clases. Dado que los parámetros definen inequívocamente algún algoritmo, una elección de los dominios de los parámetros determina alguna clase de algoritmos. Sin embargo, tal elección puede pretender ser una formalización del concepto intuitivo de algoritmo, sólo si se puede estar seguro de que para cualquier algoritmo «intuitivo» existe un algoritmo equivalente en la clase de algoritmos definida por la elección considerada. Este requisito se formula para cada formalización como una hipótesis fundamental, que, en el estado actual de los conocimientos, no puede demostrarse matemáticamente.
Las primeras formalizaciones de este tipo se deben a E.L. Post
y a A.M. Turing , , cuyas construcciones anticiparon en muchos aspectos las ideas en las que se basan los ordenadores modernos. También existen versiones formuladas por A.A. Markov ,
(cf. Algoritmo normal) y por A.N. Kolmogorov , que basó el planteamiento en complejos topológicos constructivos de cierto tipo, lo que permite expresar con mayor precisión la propiedad de «ser local» de una transformación. En cada una de estas formalizaciones, la hipótesis fundamental concuerda satisfactoriamente con la práctica. Otro argumento a favor de esta hipótesis es el hecho de que, como puede demostrarse, todas las versiones formales (de la computabilidad efectiva) que se han propuesto son equivalentes.
Como ejemplo, consideremos la formalización propuesta por Turing. En su forma original, se trataba de una descripción de un ordenador teórico que consistía en 1) una cinta infinita, dividida en celdas consecutivas, cada celda capaz de contener algún símbolo del «alfabeto de la cinta» de la máquina; y 2) un «control finito», que en cada momento del tiempo está en algún «estado» (de una lista finita de estados dada). El control finito puede moverse a lo largo de la cinta, de celda en celda, y cambiar el contenido de las celdas por las que pasa. Un programa que supervisa el movimiento del control finito constituye el algoritmo para los cálculos realizados en dicha máquina (un «algoritmo de Turing» ). Para una descripción más exacta y detallada, véase Máquina de Turing. Aquí se ofrece una exposición modernizada de la construcción de Turing. Para definir un algoritmo de Turing, uno especifica a) alfabetos disjuntos por pares $ B, D, C $, con una letra distinguida $ \lambda $ en $ D $y letras distinguidas $ \alpha $y $ \omega $ en $ C $; y b) un conjunto de pares de la forma $ \langle p \xi , \eta Tq \rangle $ donde $ p, q \in C $, $ \xi , \eta \in B \cup D $, mientras $ T $ es uno de los tres símbolos $ -, 0, + $; en este conjunto (que se llama programa) no hay dos pares con la misma primera coordenada. Las posibles entradas y las posibles salidas son palabras sobre $ B $, mientras que los posibles resultados intermedios son palabras sobre $ B \cup D \cup C $que no contienen más de una letra de $ C $. La regla de inicio es que la palabra inicial $ P $ se convierte en la palabra $ \lambda \alpha P \lambda $. La regla de terminación es que un resultado intermedio que contiene $ \omega $ es final. La regla de recuperación de la salida es que la salida es la secuencia de letras del resultado intermedio final que sigue a $ \omega $ y precede a la primera letra que no pertenece a $ B $. La regla de transformación que convierte $ A $ en $ A ^ \prime $ es la siguiente. La letra $ \lambda $ se escribe a la izquierda y a la derecha de $ A $; en la palabra así formada, la parte de la forma $ \epsilon p \xi $, donde $ p \in C $, $ \epsilon \xi \in B \cup D $, se sustituye por una palabra $ Q $ de acuerdo con la regla: se busca en el programa un par con el primer término $ p \xi $; que el segundo término de este par sea $ \eta Tq $; si $ T $ es $ – $, $ Q = q \epsilon \eta $; si $ T = 0 $, $ Q = \epsilon q \eta $; si $ T $ es $ + $, $ Q = \epsilon \eta q $. La palabra producida por este intercambio es $ A ^ \prime $. Para referencias, véase , , , , ,
de Algoritmos, teoría de.
La hipótesis fundamental mencionada anteriormente se suele denominar tesis de Church-Turing o hipótesis de Turing. Esta tesis afirma que lo que puede ser efectivamente computado según la propia intuición sobre lo que constituye un proceso efectivo, también puede ser computado por una máquina de Turing, es decir, una noción formalmente definida de algoritmo. Por su propia naturaleza de identificar una noción intuitiva informal con una definición formal precisa, la tesis de Church-Turing no puede demostrarse formalmente.
Muchas formalizaciones han resultado ser equivalentes, y ninguna formalización ha resultado ser estrictamente más potente. Aparte de las formalizaciones mencionadas anteriormente, las siguientes referencias son las más estándar en Occidente: La formalización de Church de los números y las funciones computables mediante términos lambda, los esquemas recursivos generales de Kleene y el modelo de máquina de registro propuesto por J.C. Shepherdson y H.E. Sturgis, que fue ampliado a un modelo de ordenador más realista por S.A. Cook y R.A. Reckhow. Las versiones de Markov y Kolmogorov son menos conocidas. Para completar las referencias originales de Turing y Post también se dan.
| A.M. Turing, «On computable numbers, with an application to the Entscheidungsproblem» Proc. London Math.Soc. Ser. 2 , 42 (1936) pp. 230-265 | |
| A.M. Turing, «Corrections to «On computable numbers, with an application to the Entscheidungsproblem» » Proc. London Math.Soc. Ser. 2 , 43 (1937) pp. 544-546 | |
| A. Church, «An unsolvable problem of elementary number theory» Amer. J. Math. , 58 (1936) pp. 345-363 | |
| S.C. Kleene, «General recursive functions of natural numbers» Math. Ann. , 112 (1936) pp. 727-742 | |
| E.L. Post, «Formal reductions of the general combinatorial decision problem» Amer. J. Math. , 65 (1943) pp. 197-268 | |
| J.C. Shepherdson, H.E. Sturgis, «Computability of recursive functions» J. Assoc. Comp. Mach. , 10 (1963) pp. 217-255 | |
| S.A. Cook, R.A. Reckhow, «Time-bounded random access machines» J. Computer and System Sciences , 7 (1973) pp. 354-375 |