Caracterizaciones de algoritmos

Las caracterizaciones de algoritmos son intentos de formalizar el término «algoritmo» . El término «algoritmo» no cuenta con una definición formal generalmente aceptada. Investigadores ^{[ 1 ]} trabajan activamente en este problema. Este artículo presentará con mayor detalle algunas de las «caracterizaciones» de la noción de «algoritmo».

En los últimos 200 años, la definición de algoritmo se ha vuelto más compleja y detallada a medida que los investigadores han intentado precisar el término. De hecho, puede haber más de un tipo de "algoritmo". Pero la mayoría coincide en que un algoritmo tiene que ver con la definición de procesos generalizados para la creación de números enteros de "salida" a partir de otros números enteros de "entrada" —parámetros de entrada arbitrarios e infinitos, o limitados pero variables— mediante la manipulación de símbolos distinguibles (números de conteo) con conjuntos finitos de reglas que una persona puede realizar con papel y lápiz.

Los esquemas de manipulación de números más comunes, tanto en matemáticas formales como en la vida cotidiana, son: (1) las funciones recursivas calculadas por una persona con papel y lápiz, y (2) la máquina de Turing o sus equivalentes de Turing: el modelo primitivo de máquina de registro o "máquina de contador", el modelo de máquina de acceso aleatorio ^{[ 1 ]} (RAM), el modelo de máquina de programa almacenado de acceso aleatorio (RASP) y su equivalente funcional "la computadora ".

Cuando hacemos "aritmética", en realidad estamos calculando mediante el uso de "funciones recursivas" en los algoritmos abreviados que aprendimos en la escuela primaria, por ejemplo, sumar y restar.

Las pruebas de que toda "función recursiva" que podemos calcular a mano podemos computarla mediante una máquina y viceversa —nótese el uso de las palabras calcular frente a computar— son notables. Pero esta equivalencia, junto con la tesis (afirmación no probada) de que esto incluye todo cálculo/computación, explica por qué se ha puesto tanto énfasis en el uso de máquinas equivalentes a la de Turing en la definición de algoritmos específicos, y por qué la definición misma de "algoritmo" a menudo remite a "la máquina de Turing ". Esto se analiza con más detalle en la caracterización de Stephen Kleene .

A continuación se presentan resúmenes de las caracterizaciones más famosas (Kleene, Markov, Knuth), junto con aquellas que introducen elementos novedosos, elementos que amplían aún más la definición o contribuyen a una definición más precisa.

Un problema matemático y su resultado pueden considerarse como dos puntos en un espacio, y la solución consiste en una secuencia de pasos o un camino que los une. La calidad de la solución depende del camino. Puede haber más de un atributo definido para el camino, por ejemplo, longitud, complejidad de la forma, facilidad de generalización, dificultad, etc.

Existe un mayor consenso sobre la "caracterización" de la noción de "algoritmo simple".

Todos los algoritmos deben especificarse en un lenguaje formal, y la noción de simplicidad surge de la simplicidad del lenguaje. La jerarquía de Chomsky (1956) es una jerarquía de contención de clases de gramáticas formales que generan lenguajes formales . Se utiliza para clasificar lenguajes de programación y máquinas abstractas .

Desde la perspectiva de la jerarquía de Chomsky , si el algoritmo se puede especificar en un lenguaje más simple (que uno no restringido), se puede caracterizar por este tipo de lenguaje; de ​​lo contrario, es un "algoritmo no restringido" típico.

Ejemplos: un lenguaje de macros de "propósito general", como M4 , no tiene restricciones ( es Turing completo ), pero el lenguaje de macros del preprocesador C no las tiene, por lo que cualquier algoritmo expresado en el preprocesador C es un "algoritmo simple".

Véase también Relaciones entre clases de complejidad .

Las siguientes son características deseables de un algoritmo bien definido, como se analiza en Scheider y Gersting (1995):

• Operaciones inequívocas: un algoritmo debe tener pasos específicos y bien definidos. Estos pasos deben ser lo suficientemente exactos como para especificar con precisión qué hacer en cada uno de ellos.
• Bien ordenado: El orden exacto de las operaciones que se realizan en un algoritmo debe estar definido de forma concreta.
• Viabilidad: Todos los pasos de un algoritmo deben ser posibles (también conocido como efectivamente computable ).
• Entrada: un algoritmo debe ser capaz de aceptar un conjunto de entradas bien definido.
• Salida: un algoritmo debe producir algún resultado como salida, de modo que se pueda razonar sobre su corrección.
• Finitud: un algoritmo debe terminar después de un número finito de instrucciones. ^{[ 2 ]}

Entre las propiedades deseables de ciertos algoritmos se incluyen la eficiencia en cuanto a espacio y tiempo , la generalidad (es decir, la capacidad de manejar muchas entradas) o el determinismo .

A principios de 1870, W. Stanley Jevons presentó una "Máquina Lógica" (Jevons 1880:200) para analizar un silogismo u otra forma lógica , por ejemplo, un argumento reducido a una ecuación booleana . Mediante lo que Couturat (1914) denominó una "especie de piano lógico ", las igualdades que representan las premisas se "tocan" en un teclado similar al de una máquina de escribir. Cuando se han "tocado" todas las premisas, el panel muestra solo aquellos constituyentes cuya suma es igual a 1, es decir, su totalidad lógica. Este método mecánico tiene la ventaja sobre el método geométrico de Venn (Couturat 1914:75).

Por su parte, John Venn , lógico contemporáneo de Jevons, no se mostró muy entusiasmado, opinando que «no me parece que ningún artilugio conocido actualmente o que probablemente se descubra merezca realmente el nombre de máquina lógica» (cursivas añadidas, Venn 1881:120). Pero resulta históricamente útil para el desarrollo de la noción de «algoritmo» su explicación de su reacción negativa con respecto a una máquina que «pueda cumplir un propósito realmente valioso al permitirnos evitar un trabajo que de otro modo sería inevitable».

(1) "Primero, está la declaración de nuestros datos en un lenguaje lógico preciso",

(2) "En segundo lugar, tenemos que poner estas afirmaciones en una forma adecuada para que el motor funcione con ellas; en este caso, la reducción de cada proposición a sus negaciones elementales",

(3) "En tercer lugar, está la combinación o tratamiento adicional de nuestras instalaciones después de dicha reducción",

(4) "Finalmente, los resultados deben interpretarse o leerse. Esto último generalmente da pie a mucha habilidad y sagacidad."

Concluye que "no veo que ninguna máquina pueda ayudarnos excepto en el tercero de estos pasos; por lo que parece muy dudoso que algo de este tipo realmente merezca el nombre de máquina lógica." (Venn 1881:119–121).

Esta sección es más larga y detallada que las demás debido a su importancia para el tema: Kleene fue el primero en proponer que todos los cálculos/computaciones —de cualquier tipo, la totalidad de ellos— pueden ser equivalentes (i) calculados mediante el uso de cinco " operadores recursivos primitivos " más un operador especial llamado operador mu , o ser (ii) computados mediante las acciones de una máquina de Turing o un modelo equivalente.

Además, opinó que cualquiera de estas dos opciones serviría como definición de algoritmo .

Un lector que se enfrente por primera vez a las siguientes palabras podría confundirse, por lo que conviene ofrecer una breve explicación. Cálculo significa realizado a mano, computación significa realizado por una máquina de Turing (o equivalente). (A veces, el autor confunde los términos). Una "función" puede considerarse como una "caja de entrada-salida" en la que se introducen números naturales llamados "argumentos" o "parámetros" (pero solo los números naturales, incluido el 0, es decir, los enteros no negativos) y se obtiene un único entero no negativo (conocido convencionalmente como "la respuesta"). Imaginemos la "caja de funciones" como un pequeño hombre que calcula a mano mediante "recursión general" o que realiza cálculos con una máquina de Turing (o una máquina equivalente).

«Efectivamente calculable/computable» es más genérico y significa «calculable/computable mediante algún procedimiento, método, técnica... lo que sea...». «Recursivo general» era la forma en que Kleene escribía lo que hoy se denomina simplemente «recursión»; sin embargo, la «recursión primitiva» —el cálculo mediante los cinco operadores recursivos— es una forma menor de recursión que carece de acceso al sexto operador mu, adicional, que solo se necesita en raras ocasiones. Por lo tanto, en la mayoría de los casos, solo se requieren las «funciones recursivas primitivas».

Andrey Markov Jr. (1954) proporcionó la siguiente definición de algoritmo:

"1. En matemáticas, "algoritmo" se entiende comúnmente como una prescripción exacta que define un proceso computacional, el cual conduce desde diversos datos iniciales hasta el resultado deseado..."

"Las siguientes tres características son propias de los algoritmos y determinan su papel en las matemáticas:

"a) la precisión de la prescripción, que no deja lugar a la arbitrariedad, y su comprensibilidad universal: la definitud del algoritmo;

"b) la posibilidad de partir de datos iniciales, que pueden variar dentro de límites determinados: la generalidad del algoritmo;

"c) la orientación del algoritmo hacia la obtención de un resultado deseado, que efectivamente se obtiene al final con los datos iniciales adecuados: la conclusividad del algoritmo." (p. 1)

Admitió que esta definición «no pretende ser matemáticamente precisa» (p.  1). Su monografía de 1954 fue su intento de definir algoritmo con mayor exactitud; consideró que su definición resultante —su algoritmo «normal»— era «equivalente al concepto de función recursiva » (p.  3). Su definición incluía cuatro componentes principales (Capítulo II.3, págs.  63 y siguientes):

"1. Pasos elementales separados, cada uno de los cuales se realizará de acuerdo con una de las reglas [de sustitución]... [reglas dadas al principio]

"2. ... pasos de naturaleza local ... [Por lo tanto, el algoritmo no cambiará más de un cierto número de símbolos a la izquierda o a la derecha de la palabra/símbolo observado]

"3. Reglas para las fórmulas de sustitución... [llamó a la lista de estas "el esquema" del algoritmo]

"4. ...un medio para distinguir una "sustitución final" [es decir, un estado o estados "terminales/finales" distinguibles]

En su Introducción, Markov observó que «la importancia fundamental para las matemáticas» de los esfuerzos por definir algoritmo con mayor precisión radicaría «en la relación con el problema de una base constructiva para las matemáticas» (p.  2). Ian Stewart (véase Encyclopædia Britannica) comparte una opinión similar: «... el análisis constructivo se inscribe en el mismo espíritu algorítmico que la informática...». Para más información, véase matemáticas constructivas e intuicionismo .

Distinguibilidad y localidad : ambas nociones aparecieron por primera vez con Turing (1936-1937).

«Los nuevos cuadrados observados deben ser inmediatamente reconocibles por la computadora [ sic : en 1936, una computadora era una persona]. Creo que es razonable suponer que solo pueden ser cuadrados cuya distancia al cuadrado inmediatamente observado más cercano no exceda una cierta cantidad fija. Supongamos que cada uno de los nuevos cuadrados observados se encuentra a una distancia de L cuadrados de uno de los cuadrados observados previamente.» (Turing (1936), pág. 136 en Davis, ed., Undecidible ).

La localidad aparece de forma destacada en la obra de Gurevich y Gandy (1980) (a quienes Gurevich cita). El "Cuarto Principio para los Mecanismos" de Gandy es "El Principio de Causalidad Local":

Llegamos ahora al más importante de nuestros principios. En el análisis de Turing, el requisito de que la acción dependiera únicamente de una porción limitada del registro se basaba en una limitación humana. Nosotros la sustituimos por una limitación física que denominamos principio de causalidad local. Su justificación reside en la velocidad finita de propagación de efectos y señales: la física contemporánea rechaza la posibilidad de una acción instantánea a distancia. (Gandy (1980), pág. 135 en J. Barwise et al.)

1936 : Una cita bastante famosa de Kurt Gödel aparece en una "Observación añadida en las pruebas [de la publicación original en alemán]" en su artículo "Sobre la longitud de las pruebas", traducido por Martin Davis, que aparece en las páginas  82-83 de The Undecidible . Varios autores —Kleene, Gurevich, Gandy, etc.— han citado lo siguiente:

"Así pues, el concepto de "computable" es, en cierto sentido definido, "absoluto", mientras que prácticamente todos los demás conceptos metamatemáticos conocidos (por ejemplo, demostrable, definible, etc.) dependen esencialmente del sistema con respecto al cual se definen." (p. 83)

1963 : En una "Nota" fechada el 28 de agosto de 1963, añadida a su famoso artículo Sobre proposiciones formalmente indecidibles (1931), Gödel afirma (en una nota a pie de página) su creencia de que los " sistemas formales " tienen "la propiedad característica de que el razonamiento en ellos, en principio, puede ser completamente reemplazado por dispositivos mecánicos" (pág.  616 en van Heijenoort). "...debido al trabajo de A. M. Turing, ahora se puede dar una definición precisa e incuestionablemente adecuada de la noción general de sistema formal [y] ahora es posible una versión completamente general de los Teoremas VI y XI." (pág.  616). En una nota de 1964 a otra obra, expresa la misma opinión con mayor contundencia y detalle.

1964 : En un epílogo, fechado en 1964, a un artículo presentado al Instituto de Estudios Avanzados en la primavera de 1934, Gödel amplió su convicción de que los "sistemas formales" son aquellos que pueden ser mecanizados:

"Como consecuencia de avances posteriores, en particular del hecho de que, gracias al trabajo de A. M. Turing, ahora se puede dar una definición precisa e indudablemente adecuada del concepto general de sistema formal... El trabajo de Turing ofrece un análisis del concepto de "procedimiento mecánico" (también conocido como "algoritmo", "procedimiento computacional" o "procedimiento combinatorio finito"). Se demuestra que este concepto es equivalente al de una "máquina de Turing".* Un sistema formal puede definirse simplemente como cualquier procedimiento mecánico para producir fórmulas, llamadas fórmulas demostrables..." (pág. 72 en Martin Davis, ed., The Undecidable : "Postscriptum" a "On Undecidable Propositions of Formal Mathematical Systems", que aparece en la pág. 39, loc. cit.)

El * indica una nota a pie de página en la que Gödel cita los artículos de Alan Turing (1937) y Emil Post (1936) y luego hace la siguiente afirmación intrigante:

"En cuanto a definiciones equivalentes anteriores de computabilidad, que sin embargo son mucho menos adecuadas para nuestro propósito, véase Alonzo Church , Am. J. Math., vol. 58 (1936) [que aparece en The Undecidable , págs. 100-102]).

Las definiciones de Church abarcan la llamada " recursión " y el " cálculo lambda " (es decir, las funciones λ-definibles). Su nota al pie 18 dice que discutió la relación entre "calculabilidad efectiva" y "recursividad" con Gödel, pero que cuestionó de forma independiente la "calculabilidad efectiva" y la "λ-definibilidad".

"Ahora definimos la noción... de una función efectivamente calculable de enteros positivos identificándola con la noción de una función recursiva de enteros positivos ¹⁸ (o de una función λ-definible de enteros positivos.

"Ya se ha señalado que, para cada función de enteros positivos que sea efectivamente calculable en el sentido que se acaba de definir, existe un algoritmo para el cálculo de su valor."

"Por el contrario, es cierto..." (pág. 100, Lo indecidible).

De esto y de lo que sigue se desprende que, en lo que respecta a Gödel, la máquina de Turing era suficiente y el cálculo lambda era "mucho menos adecuado". Continúa señalando que, en cuanto a las limitaciones de la razón humana, aún no hay una conclusión definitiva:

(«Nótese que la cuestión de si existen procedimientos finitos no mecánicos** que no sean equivalentes a ningún algoritmo, no tiene absolutamente nada que ver con la adecuación de la definición de "sistema formal" y de "procedimiento mecánico"). (p. 72, loc. cit.)

"(Para las teorías y los procedimientos en el sentido más general indicado en la nota al pie ** la situación puede ser diferente. Cabe señalar que los resultados mencionados en la posdata no establecen límites para las capacidades de la razón humana, sino más bien para las potencialidades del formalismo puro en matemáticas.) (p. 73 loc. cit.)

Nota al pie **: "Es decir, aquellas que implican el uso de términos abstractos en función de su significado. Véase mi artículo en Dial. 12(1958), pág. 280." (esta nota al pie aparece en la pág. 72, loc. cit.).

Minsky (1967) afirma sin rodeos que "un algoritmo es un procedimiento eficaz" y se niega a utilizar la palabra "algoritmo" más adelante en su texto; de hecho, su índice deja claro lo que piensa sobre "Algoritmo, sinónimo de procedimiento eficaz" (p.  311):

«Utilizaremos este último término [un procedimiento eficaz ] más adelante. Los términos son prácticamente sinónimos, pero existen varios matices de significado que se utilizan en diferentes contextos, especialmente para "algoritmo"» (cursiva en el original, p. 105).

Otros autores (véase Knuth más abajo) utilizan la expresión "procedimiento eficaz". Esto nos lleva a preguntarnos: ¿Cuál es la noción de Minsky de "procedimiento eficaz"? Comienza diciendo:

"...un conjunto de reglas que nos dicen, momento a momento, precisamente cómo comportarnos" (p. 106)

Pero reconoce que esto es objeto de críticas:

"...la crítica de que la interpretación de las reglas queda a cargo de alguna persona o agente" (p. 106)

¿Su perfeccionamiento? «Especificar, junto con el enunciado de las reglas, los detalles del mecanismo que las interpretará ». Para evitar el engorroso proceso de «tener que repetirlo para cada procedimiento individual», espera identificar una «familia razonablemente uniforme de mecanismos que cumplan las reglas». Su «formulación»:

"(1) un lenguaje en el que se deben expresar conjuntos de reglas de comportamiento, y

"(2) una sola máquina que pueda interpretar instrucciones en el lenguaje y así llevar a cabo los pasos de cada proceso especificado." (cursiva en el original, todas las citas corresponden a este párrafo, pág. 107)

Sin embargo, al final, le sigue preocupando que «quede un aspecto subjetivo en el asunto. Diferentes personas pueden no estar de acuerdo sobre si un determinado procedimiento debe considerarse eficaz» (p.  107).

Pero Minsky no se desanima. Inmediatamente introduce "El análisis de Turing del proceso de computación" (su capítulo 5.2). Cita lo que él llama " la tesis de Turing ".

"Cualquier proceso que pueda llamarse naturalmente un procedimiento efectivo puede ser realizado por una máquina de Turing" (p. 108. (Minsky comenta que en una forma más general esto se llama " tesis de Church ").

Tras un análisis del «Argumento de Turing» (capítulo 5.3), observa que la «equivalencia de muchas formulaciones intuitivas» de Turing, Church, Kleene, Post y Smullyan «...nos lleva a suponer que realmente existe aquí una noción "objetiva" o "absoluta". Como lo expresó Rogers [1959]:

"En este sentido, la noción de función efectivamente computable es uno de los pocos conceptos 'absolutos' producidos por el trabajo moderno en los fundamentos de las matemáticas" (Minsky, pág. 111, citando a Rogers, Hartley Jr. (1959) The present theory of Turing machine computability , J. SIAM 7, 114-130).

En su obra de 1967, *Theory of Recursive Functions and Effective Computability*, Hartley Rogers caracteriza el término "algoritmo" aproximadamente como "un procedimiento administrativo (es decir, determinista, de contabilidad)... aplicado a... entradas simbólicas y que eventualmente producirá, para cada entrada, una salida simbólica correspondiente " (p.  1). A continuación, describe la noción "en términos aproximados e intuitivos" como poseedora de 10 "características", de las cuales afirma que "prácticamente todos los matemáticos estarían de acuerdo [con] 5" (p.  2). Las 5 restantes, según él, "son menos obvias que las *1 a *5 y sobre las cuales podríamos encontrar un acuerdo menos general" (p.  3).

Las 5 "obvias" son:

• 1 Un algoritmo es un conjunto de instrucciones de tamaño finito,
• 2 Existe un agente informático capaz,
• 3 "Existen mecanismos para realizar, almacenar y recuperar los pasos de un cálculo".
• 4 Dados los datos #1 y #2, el agente calcula de forma "discreta y gradual" sin utilizar métodos continuos ni dispositivos analógicos.
• 5 El agente computacional lleva adelante el cálculo "sin recurrir a métodos o dispositivos aleatorios, por ejemplo, dados" (en una nota al pie, Rogers se pregunta si los puntos 4 y 5 son realmente lo mismo).

Los 5 restantes que abre a debate son:

• 6. No hay límite fijo en el tamaño de las entradas,
• 7 No hay límite fijo en el tamaño del conjunto de instrucciones,
• 8 No hay límite fijo en la cantidad de almacenamiento de memoria disponible,
• 9 Un límite finito fijo en la capacidad o habilidad del agente computacional (Rogers ilustra con un ejemplo mecanismos simples similares a una máquina Post-Turing o una máquina contadora ),
• 10. Un límite para la duración del cálculo: "¿Deberíamos tener alguna idea, 'de antemano', de cuánto tiempo tomará el cálculo?" (p.  5). Rogers solo exige "que un cálculo termine después de un número finito de pasos; no insistimos en la capacidad a priori de estimar este número" (p.  5).

Knuth (1968, 1973) ha dado una lista de cinco propiedades que son ampliamente aceptadas como requisitos para un algoritmo:

1. Finitud : "Un algoritmo siempre debe terminar después de un número finito de pasos... un número muy finito, un número razonable".
2. Definitividad : "Cada paso de un algoritmo debe estar definido con precisión; las acciones a realizar deben especificarse de forma rigurosa e inequívoca para cada caso".
3. Entrada : "...cantidades que se le proporcionan inicialmente antes de que comience el algoritmo. Estas entradas se toman de conjuntos de objetos específicos".
4. Salida : "...cantidades que tienen una relación específica con las entradas"
5. Eficacia : "...todas las operaciones que se deben realizar en el algoritmo deben ser lo suficientemente básicas como para que, en principio, puedan ser realizadas con exactitud y en un tiempo finito por una persona que utilice papel y lápiz".

Knuth ofrece como ejemplo el algoritmo euclidiano para determinar el máximo común divisor de dos números naturales (véase Knuth, vol. 1, pág.  2).

Knuth admite que, si bien su descripción de un algoritmo puede ser intuitivamente clara, carece de rigor formal, ya que no está del todo claro qué significa "precisamente definido", o "especificado rigurosamente y sin ambigüedades", o "suficientemente básico", etc. Hace un esfuerzo en esta dirección en su primer volumen, donde define en detalle lo que él llama el " lenguaje de máquina " para su "mítico MIX ... la primera computadora poliinsaturada del mundo" (págs.  120 y siguientes). Muchos de los algoritmos en sus libros están escritos en el lenguaje MIX. También utiliza diagramas de árbol , diagramas de flujo y diagramas de estados .

La "calidad" de un algoritmo, los "mejores" algoritmos : Knuth afirma que "en la práctica, no solo queremos algoritmos, queremos buenos algoritmos...". Sugiere que algunos criterios para evaluar la calidad de un algoritmo son el número de pasos necesarios para su ejecución, su "adaptabilidad a las computadoras, su simplicidad y elegancia, etc.". Dados varios algoritmos para realizar el mismo cálculo, ¿cuál es el "mejor"? A este tipo de investigación la denomina "análisis algorítmico: dado un algoritmo, determinar sus características de rendimiento" (todas las citas provienen de este párrafo: Knuth, vol. 1, pág.  7).

Stone (1972) y Knuth (1968, 1973) fueron profesores en la Universidad de Stanford al mismo tiempo, por lo que no es sorprendente que haya similitudes en sus definiciones (negrita añadida para enfatizar):

"En resumen... definimos un algoritmo como un conjunto de reglas que definen con precisión una secuencia de operaciones, de manera que cada regla sea efectiva y definida, y que la secuencia finalice en un tiempo finito." (negrita añadida, pág. 8)

Stone es notable por su análisis detallado de lo que constituye una regla "efectiva": su robot , o persona que actúa como robot, debe tener cierta información y habilidades en su interior, y si no, la información y la habilidad deben proporcionarse en "el algoritmo":

"Para que las personas sigan las reglas de un algoritmo, estas deben formularse de manera que puedan seguirse de forma automática, como si fueran robots , es decir, sin necesidad de pensar... Sin embargo, si las instrucciones [para resolver la ecuación cuadrática, su ejemplo] deben ser obedecidas por alguien que sabe realizar operaciones aritméticas pero no sabe cómo extraer una raíz cuadrada, entonces también debemos proporcionar un conjunto de reglas para extraer una raíz cuadrada a fin de satisfacer la definición de algoritmo" (págs. 4-5).

Además, «… no todas las instrucciones son aceptables , porque pueden requerir que el robot tenga habilidades que van más allá de lo que consideramos razonable ». Da el ejemplo de un robot al que se le pregunta si Enrique VIII fue rey de Inglaterra y debe imprimir 1 si la respuesta es sí y 0 si es no, pero no se le ha proporcionado previamente esta información. Y peor aún, si se le pregunta si Aristóteles fue rey de Inglaterra y solo se le han proporcionado cinco nombres, no sabría cómo responder. Por lo tanto:

“Una definición intuitiva de una secuencia de instrucciones aceptable es aquella en la que cada instrucción está definida con precisión, de manera que se garantiza que el robot podrá obedecerla ” (p. 6).

Después de proporcionarnos su definición, Stone introduce el modelo de máquina de Turing y afirma que el conjunto de quíntuplas que son las instrucciones de la máquina son “un algoritmo... conocido como programa de máquina de Turing” (p.  9). Inmediatamente después, continúa diciendo que “un cálculo de una máquina de Turing se describe al afirmar:

"1. El alfabeto de cintas

"2. La forma en que se presentan los parámetros [de entrada] en la cinta.

"3. El estado inicial de la máquina de Turing

"4. La forma en que las respuestas [salida] se representarán en la cinta cuando la máquina de Turing se detenga. "

"5. El programa de la máquina" (cursiva añadida, pág. 10)

Esta prescripción precisa de lo que se requiere para "un cálculo" está en consonancia con lo que seguirá en la obra de Blass y Gurevich.

"Un cálculo es un proceso mediante el cual partimos de objetos dados inicialmente, llamados entradas , siguiendo un conjunto fijo de reglas, denominado programa, procedimiento o algoritmo , a través de una serie de pasos , y llegamos al final de estos pasos con un resultado final, llamado salida . El algoritmo , como conjunto de reglas que proceden de las entradas a la salida, debe ser preciso y definido, con cada paso sucesivo claramente determinado. El concepto de computabilidad se refiere a aquellos objetos que pueden especificarse, en principio, mediante cálculos..." (cursiva en el original, negrita añadida en la pág. 3)

Mientras estudiaba en Princeton a mediados de la década de 1960, David Berlinski fue alumno de Alonzo Church (véase pág.  160). Su libro del año 2000, The Advent of the Algorithm: The 300-year Journey from an Idea to the Computer, contiene la siguiente definición de algoritmo :

" En palabras del lógico:

" un algoritmo es

un procedimiento finito,

escrito en un vocabulario simbólico fijo,

regidos por instrucciones precisas,

moviéndose en pasos discretos, 1, 2, 3, . . .,

cuya ejecución no requiere perspicacia ni inteligencia,

intuición, inteligencia o perspicacia,

y que tarde o temprano llega a su fin. (negrita y cursiva en el original, pág. xviii)

Una lectura atenta de Gurevich (2000) lleva a concluir (¿inferir?) que cree que «un algoritmo» es en realidad «una máquina de Turing» o «una máquina de punteros » que realiza un cálculo. Un «algoritmo» no es simplemente la tabla de símbolos que guía el comportamiento de la máquina, ni es solo una instancia de una máquina que realiza un cálculo con un conjunto particular de parámetros de entrada, ni es una máquina adecuadamente programada y apagada; más bien, un algoritmo es la máquina que realiza cualquier cálculo del que sea capaz . Gurevich no lo afirma explícitamente, por lo que, tal como se ha formulado anteriormente, esta conclusión (¿inferencia?) está sin duda abierta a debate.

"...todo algoritmo puede ser simulado por una máquina de Turing... un programa puede ser simulado y, por lo tanto, dotado de un significado preciso por una máquina de Turing." (p. 1)

Se suele pensar que Church [1936] y Turing [1936] resolvieron el problema de formalizar la noción de algoritmo secuencial. Por ejemplo, según Savage [1987], un algoritmo es un proceso computacional definido por una máquina de Turing. Church y Turing no resolvieron el problema de formalizar la noción de algoritmo secuencial. En cambio, proporcionaron formalizaciones (diferentes pero equivalentes) de la noción de función computable, y un algoritmo es más que la función que calcula. (cursivas añadidas en la pág. 3)

"Por supuesto, las nociones de algoritmo y función computable están íntimamente relacionadas: por definición, una función computable es una función computable mediante un algoritmo. . . . (p. 4)

En Blass y Gurevich 2002, los autores invocan un diálogo entre "Quisani" ("Q") y "Autores" (A), utilizando a Yiannis Moshovakis como contrapunto, donde declaran sin rodeos:

" A: Para delimitar la discrepancia, mencionemos primero dos puntos de acuerdo. Primero, hay algunas cosas que son obviamente algoritmos según cualquier definición: máquinas de Turing, máquinas de estados abstractos (ASM) de tiempo secuencial, etc. Segundo, en el otro extremo están las especificaciones que no se considerarían algoritmos bajo ninguna definición, ya que no indican cómo calcular nada. La cuestión es cuán detallada debe ser la información para que se considere un algoritmo. Moshovakis admite algunas cosas que nosotros llamaríamos solo especificaciones declarativas, y probablemente usaría la palabra "implementación" para lo que nosotros llamamos algoritmos." (párrafos unidos para facilitar la lectura, 2002:22)

Este uso de la palabra "implementación" va directo al meollo de la cuestión. Al principio del artículo, Q expone su interpretación de Moshovakis:

«Probablemente pensaría que tu trabajo práctico [Gurevich trabaja para Microsoft] te obliga a pensar más en implementaciones que en algoritmos. Está bastante dispuesto a identificar las implementaciones con las máquinas, pero dice que los algoritmos son algo más general. En resumen, tú dices que un algoritmo es una máquina y Moschovakis dice que no lo es.» (2002:3)

Pero los autores titubean aquí, diciendo "[C]eguámonos con 'algoritmo' y 'máquina'", y el lector queda, una vez más, confundido. Tenemos que esperar hasta Dershowitz y Gurevich 2007 para obtener el siguiente comentario a pie de página:

"... Sin embargo, si se acepta el punto de vista de Moshovakis, entonces es la "implementación" de algoritmos lo que nos hemos propuesto caracterizar." (cf. nota al pie 9 2007:6)

Blass y Gurevich describen su trabajo como una evolución a partir del estudio de las máquinas de Turing y las máquinas de punteros , específicamente las máquinas de Kolmogorov-Uspensky (máquinas KU), las máquinas de modificación de almacenamiento de Schönhage (SMM) y los autómatas de enlace definidos por Knuth. También se menciona el trabajo de Gandy y Markov como precursores influyentes.

Gurevich ofrece una definición "fuerte" de algoritmo (énfasis añadido):

"...El argumento informal de Turing a favor de su tesis justifica una tesis más sólida: todo algoritmo puede ser simulado por una máquina de Turing ... En la práctica, sería ridículo... [Sin embargo,] ¿se pueden generalizar las máquinas de Turing de modo que cualquier algoritmo, por muy abstracto que sea, pueda ser modelado por una máquina generalizada?... Pero supongamos que existen tales máquinas de Turing generalizadas. ¿Cuáles serían sus estados?... una estructura de primer orden ... un conjunto de instrucciones pequeño y particular basta en todos los casos... la computación como una evolución del estado ... podría ser no determinista... puede interactuar con su entorno... [podría ser] paralela y multiagente... [podría tener] semántica dinámica ... [los dos fundamentos de su trabajo son:] la tesis de Turing... [y] la noción de estructura (de primer orden) de [Tarski 1933]" (Gurevich 2000, págs. 1-2)

La frase anterior, «computación como evolución del estado», difiere notablemente de la definición de Knuth y Stone: el «algoritmo» como programa de una máquina de Turing. Más bien, corresponde a lo que Turing denominó configuración completa (véase la definición de Turing en «Indecidible», pág.  118), e incluye tanto la instrucción actual (estado) como el estado de la cinta. [Véase Kleene (1952), pág.  375, donde muestra un ejemplo de una cinta con 6 símbolos —todos los demás cuadrados están en blanco— y cómo «gödelizar» su estado combinado de tabla y cinta].

En los ejemplos de algoritmos vemos de primera mano la evolución del estado .

El filósofo Daniel Dennett analiza la importancia de la evolución como un proceso algorítmico en su libro de 1995, La peligrosa idea de Darwin . Dennett identifica tres características clave de un algoritmo:

• Neutralidad del sustrato : un algoritmo se basa en su estructura lógica . Por lo tanto, la forma particular en que se manifiesta un algoritmo no es importante (el ejemplo de Dennett es la división larga: funciona igual de bien en papel, en pergamino, en una pantalla de ordenador, con luces de neón o en mensajes escritos en el cielo). (p.  51)
• Falta de consciencia subyacente : por muy complejo que sea el resultado final del proceso algorítmico, cada paso del algoritmo es lo suficientemente simple como para ser ejecutado por un dispositivo mecánico no consciente. El algoritmo no requiere un «cerebro» para su mantenimiento u operación. «La analogía habitual en los libros de texto señala que los algoritmos son una especie de recetas , diseñadas para ser seguidas por cocineros novatos » (p.  51).
• Resultados garantizados : Si el algoritmo se ejecuta correctamente, siempre producirá los mismos resultados. "Un algoritmo es una receta infalible." (p.  51)

Es sobre la base de este análisis que Dennett concluye que "Según Darwin, la evolución es un proceso algorítmico" (p.  60).

Sin embargo, en la página anterior se ha arriesgado mucho más. En el contexto de su capítulo titulado "Los procesos como algoritmos", afirma:

"Pero entonces... ¿hay algún límite a lo que se puede considerar un proceso algorítmico? Supongo que la respuesta es NO; si quisieras, podrías tratar cualquier proceso a nivel abstracto como un proceso algorítmico... Si lo que te resulta desconcertante es la uniformidad de los granos de arena [del océano] o la resistencia de la hoja [de acero templado], una explicación algorítmica satisfará tu curiosidad, y será la verdad...

«Por muy impresionantes que sean los resultados de un algoritmo, el proceso subyacente siempre consiste simplemente en una serie de pasos individuales [ sic ] sin sentido que se suceden sin la ayuda de ninguna supervisión inteligente; son "automáticos" por definición: el funcionamiento de un autómata.» (p. 59)

De lo anterior no queda claro si Dennett afirma que el mundo físico por sí mismo y sin observadores es intrínsecamente algorítmico (computacional) o si es un observador que procesa símbolos el que añade "significado" a las observaciones.

Daniel Dennett es partidario de la inteligencia artificial fuerte : la idea de que la estructura lógica de un algoritmo es suficiente para explicar la mente . John Searle , creador del experimento mental de la habitación china , afirma que « la sintaxis [es decir, la estructura lógica] no es suficiente por sí sola para el contenido semántico [es decir, el significado]» ( Searle 2002 , p. 16) . En otras palabras, el «significado» de los símbolos es relativo a la mente que los utiliza; un algoritmo —una construcción lógica— por sí solo es insuficiente para la mente. 

Searle advierte a quienes afirman que los procesos algorítmicos (computacionales) son intrínsecos a la naturaleza (por ejemplo, cosmólogos, físicos, químicos, etc.):

La computación [...] es relativa al observador, y esto se debe a que la computación se define en términos de manipulación de símbolos, pero la noción de un "símbolo" no es una noción de física o química. Algo es un símbolo solo si se usa, se trata o se considera como tal. El argumento de la habitación china demostró que la semántica no es intrínseca a la sintaxis. Pero lo que esto demuestra es que la sintaxis no es intrínseca a la física. [...] Algo es un símbolo solo en relación con algún observador, usuario o agente que le asigna una interpretación simbólica [...] se puede asignar una interpretación computacional a cualquier cosa. Pero si la pregunta es: "¿Es la conciencia intrínsecamente computacional?", la respuesta es: nada es intrínsecamente computacional [cursiva añadida para enfatizar]. La computación existe solo en relación con algún agente u observador que impone una interpretación computacional a algún fenómeno. Este es un punto obvio. Debería haberlo visto hace diez años, pero no lo hice.

Para ver ejemplos de este método de especificación aplicado al algoritmo de suma "m+n", consulte Ejemplos de algoritmos .

Un ejemplo en Boolos-Burgess-Jeffrey (2002) (págs.  31-32) demuestra la precisión requerida en la especificación completa de un algoritmo, en este caso para sumar dos números: m+n. Es similar a los requisitos de Stone mencionados anteriormente.

(i) Han analizado el papel del "formato numérico" en el cálculo y han seleccionado la "notación de conteo" para representar los números:

"Ciertamente, el cálculo puede ser más difícil en la práctica con algunas notaciones que con otras... Pero... en principio es posible hacerlo con cualquier otra notación, simplemente traduciendo los datos... Para definir con rigor la noción de computabilidad, resulta conveniente utilizar la notación monádica o de conteo" (págs. 25-26).

(ii) Al comienzo de su ejemplo, especifican que la máquina que se utilizará en el cálculo es una máquina de Turing . Previamente especificaron (pág.  26) que la máquina de Turing será de la variedad de 4-tuplas, en lugar de 5-tuplas. Para más información sobre esta convención, véase Máquina de Turing .

(iii) Anteriormente, los autores especificaron que la posición del cabezal de lectura/escritura se indicará mediante un subíndice a la derecha del símbolo escaneado. Para más información sobre esta convención, véase Máquina de Turing . (En lo sucesivo, se añade negrita para enfatizar):

"No hemos dado una definición oficial de lo que significa que una función numérica sea computable por una máquina de Turing , especificando cómo deben representarse las entradas o argumentos en la máquina, y cómo deben representarse las salidas o valores. Nuestras especificaciones para una función de k lugares de enteros positivos a enteros positivos son las siguientes:

"(a) [ Formato de número inicial: ] Los argumentos m ₁ , ... m _k , ... se representarán en notación monádica [unaria] mediante bloques de esos números de trazos, cada bloque separado del siguiente por un solo espacio en blanco, en una cinta que por lo demás está en blanco.

Ejemplo: 3+2, 111B11

"(b) [ Ubicación inicial del cabezal, estado inicial: ] Inicialmente, la máquina estará escaneando el 1 más a la izquierda en la cinta y estará en su estado inicial, estado 1.

Ejemplo: 3+2, 1 ₁ 111B11

"(c) [ Cálculo exitoso: formato de número al detenerse: ] Si la función a calcular asigna un valor n a los argumentos que se representan inicialmente en la cinta, entonces la máquina finalmente se detendrá en una cinta que contenga un bloque de trazos, y de lo contrario quedará en blanco...

Ejemplo: 3+2, 11111

"(d) [ Cálculo exitoso: posición del cabezal en la parada: ] En este caso [c] la máquina detendrá el escaneo del 1 más a la izquierda en la cinta...

Ejemplo: 3+2, 1 _n 1111

"(e) [ Cálculo fallido: fallo al detenerse o detención con formato de número no estándar: ] Si la función que se va a calcular no asigna ningún valor a los argumentos representados inicialmente en la cinta, entonces la máquina nunca se detendrá o se detendrá en alguna configuración no estándar..."(ibid)

Ejemplo: B _n 11111 o B11 _n 111 o B11111 _n

Esta especificación está incompleta: requiere la ubicación donde se deben colocar las instrucciones y su formato en la máquina.

(iv) en la TABLA de la máquina de estados finitos o, en el caso de una máquina de Turing universal en la cinta, y

(v) la tabla de instrucciones en un formato específico

Este último punto es importante. Boolos, Burgess y Jeffrey demuestran (pág.  36) que la predictibilidad de las entradas en la tabla permite "reducir" la tabla ordenando las entradas y omitiendo el estado de entrada y el símbolo. De hecho, el ejemplo de cálculo de la máquina de Turing requirió solo las 4 columnas que se muestran en la tabla siguiente (pero tenga en cuenta que estas se presentaron a la máquina en filas ):

Para ver ejemplos de este método de especificación aplicado al algoritmo de suma "m+n", consulte Ejemplos de algoritmos .

Sipser comienza definiendo "algoritmo" de la siguiente manera:

En términos informales, un algoritmo es un conjunto de instrucciones sencillas para realizar alguna tarea. De uso común en la vida cotidiana, a veces se les denomina procedimientos o recetas (cursiva en el original, p. 154).

"...a partir de ahora, nuestro verdadero enfoque está en los algoritmos. Es decir, la máquina de Turing simplemente sirve como un modelo preciso para la definición de algoritmo... solo necesitamos sentirnos lo suficientemente cómodos con las máquinas de Turing como para creer que abarcan todos los algoritmos" (p. 156).

¿Sipser quiere decir que "algoritmo" son simplemente "instrucciones" para una máquina de Turing, o es la combinación de "instrucciones + una (variedad específica de) máquina de Turing"? Por ejemplo, define las dos variantes estándar (de cinta múltiple y no determinista) de su variante particular (que no es la misma que la original de Turing) y continúa, en sus Problemas (páginas 160-161), describiendo cuatro variantes más (escritura única, cinta doblemente infinita (es decir, infinita a la izquierda y a la derecha), reinicio a la izquierda y "permanecer en lugar de a la izquierda"). Además, impone algunas restricciones. Primero, la entrada debe estar codificada como una cadena (p. 157) y dice sobre las codificaciones numéricas en el contexto de la teoría de la complejidad:

"Pero tenga en cuenta que la notación unaria para codificar números (como en el número 17 codificado por el número unario 11111111111111111) no es razonable porque es exponencialmente mayor que las codificaciones verdaderamente razonables, como la notación en base k para cualquier k ≥ 2." (p. 259)

Van Emde Boas comenta sobre un problema similar con respecto al modelo abstracto de computación de máquina de acceso aleatorio (RAM) que a veces se usa en lugar de la máquina de Turing cuando se realiza un "análisis de algoritmos": "La ausencia o presencia de operaciones de manipulación de bits multiplicativas y paralelas es relevante para la comprensión correcta de algunos resultados en el análisis de algoritmos.

«...[N]a poca cosa existe como una extensión “inocente” del modelo RAM estándar en las medidas de tiempo uniformes; o bien solo se dispone de aritmética aditiva, o bien se podrían incluir todas las instrucciones booleanas multiplicativas y/o bit a bit razonables sobre operandos pequeños.» (Van Emde Boas, 1990:26)

Con respecto a un "lenguaje de descripción" para algoritmos, Sipser termina el trabajo que Stone y Boolos-Burgess-Jeffrey comenzaron (negrita añadida). Nos ofrece tres niveles de descripción de algoritmos de máquinas de Turing (p.  157):

Descripción de alto nivel : "en la que utilizamos prosa para describir un algoritmo, ignorando los detalles de implementación. A este nivel no es necesario mencionar cómo la máquina gestiona su cinta o cabezal".

Descripción de la implementación : "En la que utilizamos prosa para describir cómo la máquina de Turing mueve su cabezal y cómo almacena datos en su cinta. En este nivel no proporcionamos detalles sobre los estados ni la función de transición."

Descripción formal : "...el nivel de descripción más bajo y detallado... que detalla completamente los estados de la máquina de Turing, la función de transición, etc."

En Yanofsky (2011) ^{[ 3 ],} un algoritmo se define como el conjunto de programas que lo implementan: el conjunto de todos los programas se divide en clases de equivalencia. Si bien el conjunto de programas no forma una categoría, el conjunto de algoritmos sí la forma, con una estructura adicional. Las condiciones que describen la equivalencia entre dos programas resultan ser relaciones de coherencia que otorgan dicha estructura adicional a la categoría de algoritmos.

En Seiller (2024) ^{[ 4 ],} un algoritmo se define como un grafo con etiquetas en sus aristas, junto con una interpretación de las etiquetas como mapas en una estructura de datos abstracta. Esta definición se presenta junto con una definición formal de programas (y modelos de computación), lo que permite definir formalmente la noción de implementación, es decir, cuando un programa implementa un algoritmo. La noción de algoritmo así obtenida evita algunos problemas conocidos y se entiende como una especificación. En particular, un programa dado puede (y de hecho, siempre lo hace) implementar varios algoritmos. Otra característica importante del enfoque es que tiene en cuenta que un algoritmo dado puede implementarse en diferentes modelos computacionales (y posiblemente no relacionados).

• David Berlinski (2000), El advenimiento del algoritmo: El viaje de 300 años desde una idea hasta la computadora , Harcourt, Inc., San Diego, ISBN 0-15-601391-6(pbk.)
• George Boolos , John P. Burgess , Richard Jeffrey (2002), Computabilidad y lógica: cuarta edición , Cambridge University Press, Cambridge, Reino Unido. ISBN 0-521-00758-5(pbk).
• Andreas Blass y Yuri Gurevich (2003), Algorithms: A Quest for Absolute Definitions , Bulletin of European Association for Theoretical Computer Science 81, 2003. Incluye una excelente bibliografía de 56 referencias.
• Burgin, M. Algoritmos superrecursivos , Monografías en ciencias de la computación, Springer, 2005. ISBN 0-387-95569-0
• Davis, Martin (1958). Computabilidad e insolubilidad . Nueva York: McGraw-Hill Book Company, Inc.Una fuente de definiciones importantes y algunos algoritmos basados ​​en máquinas de Turing para algunas funciones recursivas.
• Davis, Martin (1965). Lo indecidible: Artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Nueva York: Raven Press.Davis ofrece comentarios antes de cada artículo. Se incluyen trabajos de Gödel , Alonzo Church , Turing , Rosser , Kleene y Emil Post .
• Dennett, Daniel (1995). La peligrosa idea de Darwin . Nueva York: Touchstone/Simon & Schuster.
• Gandy, Robin , La tesis de Church y principios para mecanismos , en J. Barwise , H.J. Keisler y K. Kunen , eds., El simposio de Kleene , North-Holland Publishing Company 1980) pp.  123–148. Los famosos "4 principios de los mecanismos [computacionales]" de Gandy incluyen el "Principio IV: El principio de causalidad local".
• Gurevich, Yuri , Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, Vol 1, no 1 (julio de 2000), páginas 77–111. Incluye una bibliografía de 33 fuentes.
• Kleene C., Stephen (1943). "Predicados y cuantificadores recursivos" . Transactions of the American Mathematical Society . 54 (1): 41– 73. doi : 10.2307/1990131 . JSTOR 1990131 . Reimpreso en The Undecidable , pág.  255 y ss. Kleene refinó su definición de "recursión general" y procedió en su capítulo "12. Teorías algorítmicas" a postular la "Tesis I" (pág.  274); más tarde repetiría esta tesis (en Kleene 1952:300) y la llamaría "Tesis de Church" (Kleene 1952:317) (es decir, la Tesis de Church ).
• Kleene, Stephen C. (1991) [1952]. Introducción a la metamatemática (Décima  ed.). North-Holland Publishing Company.Excelente fuente de referencia —accesible y legible— para los "fundamentos" matemáticos.
• Knuth, Donald E. (1973) [1968]. El arte de la programación de computadoras, segunda edición, volumen 1/Algoritmos fundamentales (2.ª  ed.). Addison-Wesley Publishing Company.El primero de los tres textos que componen la famosa serie de Knuth.
• Lewis, HR y Papadimitriou, CH Elementos de la teoría de la computación , Prentice-Hall, Upper Saddle River, NJ, 1998
• AA Markov (1954) Teoría de algoritmos . [Traducido por Jacques J. Schorr-Kon y personal de PST] Pie de imprenta Moscú, Academia de Ciencias de la URSS, 1954 [es decir, Jerusalén, Programa de Traducciones Científicas de Israel, 1961; disponible en la Oficina de Servicios Técnicos, Departamento de Comercio de EE. UU., Washington] Descripción 444 p.  28  cm. Portada añadida en ruso Traducción de las Obras del Instituto Matemático, Academia de Ciencias de la URSS, vol. 42. Título original: Teoriya algerifmov. [QA248.M2943 Biblioteca del Dartmouth College. Departamento de Comercio de EE. UU., Oficina de Servicios Técnicos, número OTS 60–51085.]
• Minsky, Marvin (1967). Computación: Máquinas finitas e infinitas (Primera  ed.). Prentice-Hall, Englewood Cliffs, NJ.Minsky amplía su "...idea de algoritmo — un procedimiento efectivo..." en el capítulo 5.1 Computabilidad, procedimientos efectivos y algoritmos. Máquinas infinitas.
• Rogers, Hartley Jr. , (1967), Teoría de las funciones recursivas y la computabilidad efectiva , MIT Press (1987), Cambridge, MA, ISBN 0-262-68052-1(pbk.)
• Searle, John (2002). Conciencia y lenguaje . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-59744-7.
• Seiller, Thomas , (2024), Informática Matemática , Tesis de habilitación, Université Sorbonne Paris Nord,.
• Sipser, Michael , (2006), Introducción a la teoría de la computación: Segunda edición , Thompson Course Technology div. de Thompson Learning, Inc. Boston, MA. ISBN 978-0-534-95097-2.
• Soare, Robert , (1995, aparecerá en las Actas del 10º Congreso Internacional de Lógica, Metodología y Filosofía de la Ciencia , 19-25 de agosto de 1995, Florencia, Italia), Computabilidad y recursión ), en la web en  ??.
• Ian Stewart , Algoritmo , Encyclopædia Britannica 2006.
• Stone, Harold S. Introducción a la organización de computadoras y estructuras de datos (  edición de 1972). McGraw-Hill, Nueva York.Véase en particular el primer capítulo titulado: Algoritmos, máquinas de Turing y programas . Su concisa definición informal: "...cualquier secuencia de instrucciones que pueda ser obedecida por un robot se denomina algoritmo " (p.  4).
• van Emde Boas, Peter (1990), "Machine Models and Simulations", pp. 3-66, publicado en Jan van Leeuwen (1990), Handbook of Theoretical Computer Science. Volumen A: Algorithms & Complexity , The MIT Press/Elsevier, 1990, ISBN 0-444-88071-2(Volumen A)