En matemáticas e informática , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita derigurosas, normalmente utilizada para resolver una clase deproblemaso para realizar uncálculo. [1]Los algoritmos se utilizan como especificaciones para realizarcálculosyprocesamiento de datos. Los algoritmos más avanzados pueden usarcondicionalespara desviar la ejecución del código a través de varias rutas (lo que se conoce comotoma de decisiones automatizada) y deducirinferencias(lo que se conoce comorazonamiento automatizado), lograndoeventualmentela automatizaciónAlan Turingya practicaba el uso metafórico de características humanas como descriptores de máquinascon términos como "memoria", "búsqueda" y "estímulo". [2]
Por el contrario, una heurística es un enfoque para la resolución de problemas que puede no estar completamente especificado o no garantizar resultados correctos u óptimos, especialmente en dominios de problemas donde no existe un resultado correcto u óptimo bien definido. [3] Por ejemplo, los sistemas de recomendación de redes sociales se basan en heurísticas de tal manera que, aunque se caracterizan ampliamente como "algoritmos" en los medios populares del siglo XXI, no pueden ofrecer resultados correctos debido a la naturaleza del problema.
Como método eficaz , un algoritmo se puede expresar dentro de una cantidad finita de espacio y tiempo [4] y en un lenguaje formal bien definido [5] para calcular una función . [6] A partir de un estado inicial y una entrada inicial (quizás vacía ), [7] las instrucciones describen un cálculo que, cuando se ejecuta , avanza a través de un número finito [8] de estados sucesivos bien definidos, y eventualmente produce una "salida" [ 9] y terminando en un estado final final. La transición de un estado al siguiente no es necesariamente determinista ; Algunos algoritmos, conocidos como algoritmos aleatorios , incorporan entradas aleatorias. [10]
Desde la antigüedad se atestiguan procedimientos paso a paso para la resolución de problemas matemáticos. Esto incluye las matemáticas babilónicas (alrededor del 2500 a. C.), [11] las matemáticas egipcias (alrededor del 1550 a. C.), [11] las matemáticas indias (alrededor del 800 a. C. y posteriores; por ejemplo, Shulba Sutras , la escuela de Kerala y Brāhmasphuṭasiddhānta ), [12] [13] El oráculo de Ifá (alrededor del 500 a. C.), las matemáticas griegas (alrededor del 240 a. C., por ejemplo, la criba de Eratóstenes y el algoritmo euclidiano ), [14] y las matemáticas árabes (siglo IX, por ejemplo, algoritmos criptográficos para descifrar códigos basados en el análisis de frecuencia ). [15]
Alrededor del año 825, el científico y polímata iraní Muḥammad ibn Mūsā al-Khwārizmī escribió kitāb al-ḥisāb al-hindī ("Libro de computación india") y kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī ("Suma y resta en aritmética india"). Ambos textos se han perdido en el árabe original en este momento. (Sin embargo, su otro libro sobre álgebra permanece). [16]
A principios del siglo XII, aparecieron traducciones latinas de dichos textos de al-Khwarizmi que involucraban el sistema de numeración y aritmética hindú-árabe : Liber Alghoarismi de practica arismetrice (atribuido a Juan de Sevilla ) y Liber Algorismi de numero Indorum (atribuido a Adelardo de Bath ) . [17] Por la presente, alghoarismi o algorismi es la latinización del nombre de Al-Khwarizmi; el texto comienza con la frase Dixit Algorismi ("Así habló Al-Khwarizmi"). [18]
En 1240, Alejandro de Villedieu escribe un texto en latín titulado Carmen de Algorismo . Comienza con:
Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.
que se traduce en:
El algoritmo es el arte mediante el cual utilizamos actualmente esas cifras indias, que son dos por cinco.
El poema tiene unos cientos de líneas y resume el arte de calcular con los nuevos dados indios ( Tali Indorum ), o números hindúes. [19]
Alrededor de 1230, se atestigua la palabra inglesa algorism y luego por Chaucer en 1391. Los ingleses adoptaron el término francés. [20] [21]
En el siglo XV, bajo la influencia de la palabra griega ἀριθμός ( arithmos , "número"; cf. "aritmética"), la palabra latina fue alterada a algoritmus .
En 1656, en el diccionario inglés Glossographia , dice: [22]
Algorismo ([ latín ] algorismus ) el arte o uso de cifrados, o de numeración mediante cifrados; habilidad en contabilidad.
Augrime ([ latín ] algoritmus ) habilidad para contabilizar o adormecer.
En 1658, en la primera edición de The New World of English Words , dice: [23]
Algoritmo , (palabra compuesta de árabe y español ), el arte de calcular mediante cifrados.
En 1706, en la sexta edición de The New World of English Words , dice: [24]
Algoritmo , el arte de calcular o calcular mediante números, que contiene las cinco reglas principales de la aritmética, a saber. Numeración , Suma , Resta , Multiplicación y División ; a lo que se puede sumar Extracción de Raíces : También se llama Logistica Numeralis .
Algorismo , la operación práctica en las diversas partes de la aritmética engañosa o álgebra ; a veces se toma como práctica de la aritmética común mediante las diez cifras numéricas.
En 1751, en Young Algebraist's Companion , Daniel Fenning contrasta los términos algorismo y algoritmo de la siguiente manera: [25]
Algoritmo significa los primeros Principios , y Algorismo la Parte práctica, o saber poner el Algoritmo en Práctica.
Desde al menos 1811 [actualizar], se ha atestiguado que el término algoritmo significa "procedimiento paso a paso" en inglés. [26] [27]
En 1842, en el Diccionario de ciencia, literatura y arte , dice:
ALGORITMO, significa el arte de computar en referencia a algún tema en particular, o de alguna manera en particular; como algoritmo de números; El algoritmo del cálculo diferencial. [28]
En 1928, comenzó una formalización parcial del concepto moderno de algoritmos con intentos de resolver el Entscheidungsproblem (problema de decisión) planteado por David Hilbert . Las formalizaciones posteriores se enmarcaron como intentos de definir la " calculabilidad efectiva " [29] o el "método efectivo". [30] Esas formalizaciones incluyeron las funciones recursivas de Gödel – Herbrand – Kleene de 1930, 1934 y 1935, el cálculo lambda de Alonzo Church de 1936, la Formulación 1 de Emil Post de 1936 y las máquinas de Turing de Alan Turing de 1936–37. y 1939.
Una definición informal es "un conjunto de reglas que define con precisión una secuencia de operaciones", [31] [ necesita cita para verificar ] que incluiría todos los programas de computadora (incluidos los programas que no realizan cálculos numéricos) y (por ejemplo) cualquier procedimiento burocrático prescrito [32] o receta de libro de cocina . [33]
En general, un programa es un algoritmo sólo si finalmente se detiene [34] , aunque a veces los bucles infinitos pueden resultar deseables.
Un ejemplo prototípico de algoritmo es el algoritmo euclidiano , que se utiliza para determinar el máximo común divisor de dos números enteros; Un ejemplo (hay otros) se describe en el diagrama de flujo anterior y como ejemplo en una sección posterior.
Boolos, Jeffrey & 1974, 1999 ofrecen un significado informal de la palabra "algoritmo" en la siguiente cita:
Ningún ser humano puede escribir lo suficientemente rápido, o lo suficientemente largo, o lo suficientemente pequeño† (†"más y más pequeño sin límite... estarías tratando de escribir en moléculas, átomos, electrones") para enumerar todos los miembros de una conjunto enumerablemente infinito escribiendo sus nombres, uno tras otro, en alguna notación. Pero los humanos pueden hacer algo igualmente útil, en el caso de ciertos conjuntos enumerablemente infinitos: pueden dar instrucciones explícitas para determinar el enésimo miembro del conjunto , para n finitos arbitrarios . Estas instrucciones deben darse de forma bastante explícita, de forma que puedan ser seguidas por una máquina informática o por un ser humano que sólo sea capaz de realizar operaciones muy elementales con símbolos. [35]
Un "conjunto enumerablemente infinito" es aquel cuyos elementos pueden ponerse en correspondencia uno a uno con los números enteros. Así, Boolos y Jeffrey dicen que un algoritmo implica instrucciones para un proceso que "crea" números enteros de salida a partir de un número entero o números enteros de "entrada" arbitrarios que, en teoría, pueden ser arbitrariamente grandes. Por ejemplo, un algoritmo puede ser una ecuación algebraica como y = m + n (es decir, dos "variables de entrada" arbitrarias m y n que producen una salida y ), pero los intentos de varios autores de definir la noción indican que la palabra implica mucho más que esto, algo del orden de (para el ejemplo de suma):
El concepto de algoritmo también se utiliza para definir la noción de decidibilidad , noción central para explicar cómo surgen los sistemas formales a partir de un pequeño conjunto de axiomas y reglas. En lógica , el tiempo que requiere un algoritmo para completarse no se puede medir, ya que aparentemente no está relacionado con la dimensión física habitual. De estas incertidumbres, que caracterizan el trabajo en curso, se deriva la falta de disponibilidad de una definición de algoritmo que se adapte tanto al uso concreto (en cierto sentido) como al abstracto del término.
La mayoría de los algoritmos están pensados para implementarse como programas informáticos . Sin embargo, los algoritmos también se implementan por otros medios, como en una red neuronal biológica (por ejemplo, el cerebro humano implementando la aritmética o un insecto buscando comida), en un circuito eléctrico o en un dispositivo mecánico.
Los algoritmos son esenciales para la forma en que las computadoras procesan datos. Muchos programas de computadora contienen algoritmos que detallan las instrucciones específicas que una computadora debe realizar (en un orden específico) para llevar a cabo una tarea específica, como calcular los cheques de pago de los empleados o imprimir las boletas de calificaciones de los estudiantes. Por tanto, se puede considerar que un algoritmo es cualquier secuencia de operaciones que puede ser simulada por un sistema completo de Turing . Los autores que afirman esta tesis incluyen a Minsky (1967), Savage (1987) y Gurevich (2000):
Minsky: "Pero también mantendremos, con Turing... que cualquier procedimiento que pueda ser llamado "naturalmente" efectivo, puede, de hecho, realizarse mediante una máquina (simple). Aunque esto pueda parecer extremo, los argumentos... .a su favor son difíciles de refutar". [41] Gurevich: "... El argumento informal de Turing a favor de su tesis justifica una tesis más fuerte: cada algoritmo puede ser simulado por una máquina de Turing ... según Savage [1987], un algoritmo es un proceso computacional definido por una máquina de Turing". [42]
Las máquinas de Turing pueden definir procesos computacionales que no terminan. Las definiciones informales de algoritmos generalmente requieren que el algoritmo siempre termine. Este requisito hace que la tarea de decidir si un procedimiento formal es un algoritmo sea imposible en el caso general, debido a un teorema importante de la teoría de la computabilidad conocido como el problema de la detención .
Normalmente, cuando un algoritmo está asociado con el procesamiento de información, los datos se pueden leer desde una fuente de entrada, escribirse en un dispositivo de salida y almacenarse para su posterior procesamiento. Los datos almacenados se consideran parte del estado interno de la entidad que realiza el algoritmo. En la práctica, el estado se almacena en una o más estructuras de datos .
Para algunos de estos procesos computacionales, el algoritmo debe estar rigurosamente definido y especificado en la forma en que se aplica en todas las circunstancias posibles que puedan surgir. Esto significa que cualquier medida condicional debe abordarse sistemáticamente, caso por caso; los criterios para cada caso deben ser claros (y computables).
Debido a que un algoritmo es una lista precisa de pasos precisos, el orden de cálculo siempre es crucial para el funcionamiento del algoritmo. Por lo general, se supone que las instrucciones se enumeran explícitamente y se describen como que comienzan "desde arriba" y van "hacia abajo", una idea que se describe más formalmente como flujo de control .
Hasta ahora, la discusión sobre la formalización de un algoritmo ha asumido las premisas de la programación imperativa . Ésta es la concepción más común: la que intenta describir una tarea en términos discretos y "mecánicos". Asociada a esta concepción de algoritmos formalizados está la operación de asignación , que establece el valor de una variable. Se deriva de la intuición de la " memoria " como bloc de notas. A continuación se puede encontrar un ejemplo de dicha asignación.
Para conocer algunas concepciones alternativas de lo que constituye un algoritmo, consulte programación funcional y programación lógica .
Los algoritmos se pueden expresar en muchos tipos de notación, incluidos lenguajes naturales , pseudocódigo , diagramas de flujo , diagramas drakon , lenguajes de programación o tablas de control (procesadas por intérpretes ). Las expresiones de algoritmos en lenguaje natural tienden a ser detalladas y ambiguas y rara vez se utilizan para algoritmos complejos o técnicos. El pseudocódigo, los diagramas de flujo, los diagramas drakon y las tablas de control son formas estructuradas de expresar algoritmos que evitan muchas de las ambigüedades comunes en las declaraciones basadas en lenguaje natural. Los lenguajes de programación están destinados principalmente a expresar algoritmos en una forma que pueda ser ejecutada por una computadora, pero también se utilizan a menudo como una forma de definir o documentar algoritmos.
Existe una amplia variedad de representaciones posibles y se puede expresar un programa de máquina de Turing dado como una secuencia de tablas de máquina (ver máquina de estados finitos , tabla de transición de estados y tabla de control para obtener más información), como diagramas de flujo y diagramas de drakon (ver estado diagrama para obtener más información), o como una forma de código de máquina rudimentario o código ensamblador llamado "conjuntos de cuádruples" (consulte Máquina de Turing para obtener más información).
Las representaciones de algoritmos se pueden clasificar en tres niveles aceptados de descripción de la máquina de Turing, de la siguiente manera: [43]
Para ver un ejemplo del algoritmo simple "Agregar m+n" descrito en los tres niveles, consulte Ejemplos.
El diseño de algoritmos se refiere a un método o proceso matemático para la resolución de problemas y la ingeniería de algoritmos. El diseño de algoritmos forma parte de muchas teorías de solución, como la programación dinámica o divide y vencerás dentro de la investigación operativa . Las técnicas para diseñar e implementar diseños de algoritmos también se denominan patrones de diseño de algoritmos, [44] con ejemplos que incluyen el patrón de método de plantilla y el patrón decorador.
Uno de los aspectos más importantes del diseño de algoritmos es la eficiencia de los recursos (tiempo de ejecución, uso de memoria); la notación O grande se utiliza para describir, por ejemplo, el crecimiento del tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de su entrada.
Pasos típicos en el desarrollo de algoritmos:
IF test THEN GOTO step xxx, mostrado como un diamante), el GOTO incondicional (rectángulo), varios operadores de asignación (rectángulo) y HALT (rectángulo). El anidamiento de estas estructuras dentro de bloques de asignación da como resultado diagramas complejos (cf. Tausworthe 1977:100, 114).Programas "elegantes" (compactos), programas "buenos" (rápidos) : La noción de "simplicidad y elegancia" aparece informalmente en Knuth y precisamente en Chaitin :
Chaitin introduce su definición con: "Les mostraré que no se puede probar que un programa es 'elegante ' "; tal prueba resolvería el problema de la detención (ibid).
Algoritmo versus función computable mediante un algoritmo : para una función determinada pueden existir múltiples algoritmos. Esto es cierto incluso sin ampliar el conjunto de instrucciones disponibles para el programador. Rogers observa que "Es... importante distinguir entre la noción de algoritmo , es decir, procedimiento, y la noción de función computable por algoritmo , es decir, mapeo generado por procedimiento. La misma función puede tener varios algoritmos diferentes". [47]
Desafortunadamente, puede haber un equilibrio entre bondad (velocidad) y elegancia (compacidad): un programa elegante puede requerir más pasos para completar un cálculo que uno menos elegante. A continuación se muestra un ejemplo que utiliza el algoritmo de Euclides.
Computadoras (y computors), modelos de computación : Una computadora (o "computadora" humana [48] ) es un tipo restringido de máquina, un "dispositivo mecánico determinista discreto" [49] que sigue ciegamente sus instrucciones. [50] Los modelos primitivos de Melzak y Lambek [51] redujeron esta noción a cuatro elementos: (i) ubicaciones discretas y distinguibles , (ii) contadores discretos e indistinguibles [52] (iii) un agente y (iv) una lista de instrucciones que son efectivos en relación con la capacidad del agente. [53]
Minsky describe una variación más agradable del modelo "ábaco" de Lambek en sus "Bases muy simples para la computabilidad ". [54] La máquina de Minsky procede secuencialmente a través de sus cinco (o seis, dependiendo de cómo se cuenten) instrucciones a menos que un programa de cambios IF-THEN GOTO condicional o un GOTO incondicional fluyan fuera de secuencia. Además de HALT, la máquina de Minsky incluye tres operaciones de asignación (reemplazo, sustitución) [55] : CERO (por ejemplo, el contenido de la ubicación reemplazada por 0: L ← 0), SUCESOR (por ejemplo, L ← L+1) y DISMINUCIÓN (por ejemplo, L ← L-1). [56] Rara vez un programador debe escribir "código" con un conjunto de instrucciones tan limitado. Pero Minsky muestra (al igual que Melzak y Lambek) que su máquina es Turing completa con sólo cuatro tipos generales de instrucciones: GOTO condicional, GOTO incondicional, asignación/reemplazo/sustitución y HALT. Sin embargo, también se requieren algunas instrucciones de asignación diferentes (por ejemplo, DISMINUCIÓN, INCREMENTO y CERO/BORRAR/VACÍO para una máquina de Minsky) para completar Turing; su especificación exacta depende en cierta medida del diseñador. El GOTO incondicional es conveniente; se puede construir inicializando una ubicación dedicada a cero, por ejemplo, la instrucción "Z ← 0"; a partir de entonces, la instrucción IF Z=0 THEN GOTO xxx es incondicional.
Simulación de un algoritmo: lenguaje de computadora (computadora) : Knuth advierte al lector que "la mejor manera de aprender un algoritmo es probarlo... inmediatamente tome lápiz y papel y trabaje con un ejemplo". [57] Pero ¿qué pasa con una simulación o ejecución de algo real? El programador debe traducir el algoritmo a un lenguaje que el simulador/computadora/computadora pueda ejecutar efectivamente . Stone da un ejemplo de esto: al calcular las raíces de una ecuación cuadrática, la computadora debe saber cómo sacar una raíz cuadrada. Si no es así, entonces el algoritmo, para ser efectivo, debe proporcionar un conjunto de reglas para extraer una raíz cuadrada. [58]
Esto significa que el programador debe conocer un "lenguaje" que sea efectivo en relación con el agente informático de destino (computadora/computadora).
Pero, ¿qué modelo debería utilizarse para la simulación? Van Emde Boas observa que "incluso si basamos la teoría de la complejidad en máquinas abstractas en lugar de concretas, la arbitrariedad en la elección de un modelo persiste. Es en este punto donde entra la noción de simulación ". [59] Cuando se mide la velocidad, el conjunto de instrucciones importa. Por ejemplo, el subprograma del algoritmo de Euclides para calcular el resto se ejecutaría mucho más rápido si el programador tuviera disponible una instrucción de " módulo " en lugar de sólo una resta (o peor: sólo el "decremento" de Minsky).
Programación estructurada, estructuras canónicas : según la tesis de Church-Turing , cualquier algoritmo puede calcularse mediante un modelo conocido como Turing completo y, según las demostraciones de Minsky, la integridad de Turing requiere solo cuatro tipos de instrucciones: GOTO condicional, GOTO incondicional, asignación y DETENER. Kemeny y Kurtz observan que, si bien el uso "indisciplinado" de GOTO incondicionales y GOTO condicionales SI-ENTONCES puede dar como resultado un " código espagueti ", un programador puede escribir programas estructurados utilizando sólo estas instrucciones; por otro lado "también es posible, y no demasiado difícil, escribir programas mal estructurados en un lenguaje estructurado". [60] Tausworthe aumenta las tres estructuras canónicas de Böhm-Jacopini : [61] SECUENCIA, SI-ENTONCES-ELSE y MIENTRAS-HACER, con dos más: HACER MIENTRAS y CASO. [62] Un beneficio adicional de un programa estructurado es que se presta a pruebas de corrección mediante inducción matemática . [63]
Símbolos de diagrama de flujo canónicos [64] : la ayuda gráfica llamada diagrama de flujo ofrece una manera de describir y documentar un algoritmo (y un programa de computadora correspondiente a él). Al igual que el flujo del programa de una máquina Minsky, un diagrama de flujo siempre comienza en la parte superior de una página y continúa hacia abajo. Sus símbolos principales son sólo cuatro: la flecha dirigida que muestra el flujo del programa, el rectángulo (SECUENCIA, GOTO), el diamante (SI-ENTONCES-ELSE) y el punto (OR-empate). Las estructuras canónicas de Böhm-Jacopini están hechas de estas formas primitivas. Las subestructuras pueden "anidar" en rectángulos, pero sólo si se produce una única salida desde la superestructura. Los símbolos y su uso para construir las estructuras canónicas se muestran en el diagrama.
Uno de los algoritmos más simples es encontrar el número más grande en una lista de números de orden aleatorio. Encontrar la solución requiere mirar todos los números de la lista. De esto se sigue un algoritmo simple, que puede expresarse en una descripción de alto nivel en prosa inglesa, como:
Descripción de alto nivel:
Descripción (cuasi) formal: escrita en prosa pero mucho más cercana al lenguaje de alto nivel de un programa de computadora, la siguiente es la codificación más formal del algoritmo en pseudocódigo o código pidgin :
Algoritmo Número más grandeEntrada: una lista de números L .Salida: El número más grande de la lista L.
si L.size = 0 devuelve nulo el más grande ← L [0] para cada elemento en L , hazlo si el elemento > más grande , entonces el elemento más grande ← devuelve el más grande
En matemáticas , el algoritmo euclidiano o algoritmo de Euclides, es un método eficiente para calcular el máximo común divisor (MCD) de dos enteros (números), el mayor número que los divide a ambos sin resto . Lleva el nombre del antiguo matemático griego Euclides , quien lo describió por primera vez en sus Elementos ( c. 300 a. C. ). [65] Es uno de los algoritmos más antiguos de uso común. Se puede utilizar para reducir fracciones a su forma más simple y forma parte de muchos otros cálculos criptográficos y de teoría de números.
Euclides plantea el problema así: "Dados dos números que no son primos entre sí, encontrar su máxima medida común". Él define "Un número [ser] una multitud compuesta de unidades": un número de conteo, un entero positivo que no incluye el cero. "Medir" es colocar una longitud de medición más corta s sucesivamente ( q veces) a lo largo de una longitud más larga l hasta que la porción restante r sea menor que la longitud más corta s . [66] En palabras modernas, resto r = l − q × s , siendo q el cociente, o resto r es el "módulo", la parte entero-fraccional que queda después de la división. [67]
Para que el método de Euclides tenga éxito, las longitudes iniciales deben satisfacer dos requisitos: (i) las longitudes no deben ser cero, Y (ii) la resta debe ser "adecuada"; es decir, una prueba debe garantizar que el menor de los dos números se reste del mayor (o los dos pueden ser iguales para que su resta dé cero).
La prueba original de Euclides añade un tercer requisito: las dos longitudes no deben ser primas entre sí. Euclides estipuló esto para poder construir una prueba reductio ad absurdum de que la medida común de los dos números es, de hecho, la mayor . [68] Si bien el algoritmo de Nicómaco es el mismo que el de Euclides, cuando los números son primos entre sí, produce el número "1" como medida común. Entonces, para ser precisos, el siguiente es realmente el algoritmo de Nicomachus.
1599 = 650×2 + 299 650 = 299×2 + 52 299 = 52×5 + 39 52 = 39×1 + 1339 = 13×3 + 0Sólo se requieren unos pocos tipos de instrucciones para ejecutar el algoritmo de Euclides: algunas pruebas lógicas (GOTO condicional), GOTO incondicional, asignación (reemplazo) y resta.
El siguiente algoritmo está enmarcado como la versión de cuatro pasos de Knuth del de Euclides y Nicómaco, pero, en lugar de usar la división para encontrar el resto, usa restas sucesivas de la longitud más corta s de la longitud restante r hasta que r sea menor que s . La descripción de alto nivel, que se muestra en negrita, está adaptada de Knuth 1973:2–4:
APORTE :
1 [En dos ubicaciones L y S coloque los números l y s que representan las dos longitudes]:ENTRADA L, S2 [Inicializar R: hacer que la longitud restante r sea igual a la longitud inicial/inicial/de entrada l ]:R ← L
E0: [Asegúrese de que r ≥ s .]
3 [Asegúrese de que el menor de los dos números esté en S y el mayor en R]:SI R > S ENTONCESel contenido de L es el número mayor, así que omita los pasos de intercambio 4, 5 y 6:IR AL paso 7DEMÁSintercambiar el contenido de R y S.4 L ← R (este primer paso es redundante, pero es útil para una discusión posterior).5 R ← S6 S ← L
E1: [Encontrar el resto] : hasta que la longitud restante r en R sea menor que la longitud más corta s en S, reste repetidamente el número de medición s en S de la longitud restante r en R.
7 SI S > R ENTONCEShecho de medirIR A 10DEMÁSmedir de nuevo,8 R ← R − S9 [bucle restante]:IR A 7.
E2: [¿El resto es cero?] : O (i) la última medida fue exacta, el resto en R es cero y el programa puede detenerse, O (ii) el algoritmo debe continuar: la última medida dejó un resto en R menor que el número de medición en S.
10 SI R = 0 ENTONCEShechoIR AL paso 15DEMÁSCONTINÚE CON el paso 11,E3: [Intercambio syr ] : La nuez del algoritmo de Euclides. Utilice el resto r para medir lo que antes era un número s más pequeño ; L sirve como ubicación temporal.
11 L ← R12 R ← S13 S ← L14 [Repetir el proceso de medición]:IR A 7
PRODUCCIÓN :
15 [Hecho. S contiene el máximo común divisor ]:IMPRIMIR
HECHO :
16 DETENER, FINALIZAR, PARAR.La siguiente versión del algoritmo de Euclides requiere sólo seis instrucciones básicas para hacer lo que "Poco elegante" requiere trece; Peor aún, "poco elegante" requiere más tipos de instrucciones. [ aclarar ] El diagrama de flujo de "Elegante" se puede encontrar en la parte superior de este artículo. En el lenguaje básico (no estructurado), los pasos están numerados y la instrucción es la instrucción de asignación simbolizada por ←.LET [] = []
5 REM Algoritmo de Euclides para el máximo común divisor 6 PRINT "Escriba dos números enteros mayores que 0" 10 INPUT A , B 20 IF B = 0 THEN GOTO 80 30 IF A > B THEN GOTO 60 40 LET B = B - A 50 GOTO 20 60 DEJAR A = A - B 70 IR A 20 80 IMPRIMIR A 90 FINAL Cómo funciona "Elegant" : en lugar de un "bucle de Euclid" externo, "Elegant" calcula el resto de una división usando módulo y desplaza las variables A y B en cada iteración. El siguiente algoritmo se puede utilizar con lenguajes de programación de la familia C :
// Algoritmo de Euclides para el máximo común divisor int euclidAlgorithm ( int A , int B ) { A = abs ( A ); B = abdominales ( B ); si ( A == 0 || B == 0 ) { retorno 0 ; } hacer { int res = A % B ; A = B ; B = resolución ; } mientras ( B > 0 ); devolver A ; ¿Un algoritmo hace lo que su autor quiere que haga? Unos pocos casos de prueba suelen dar cierta confianza en la funcionalidad principal. Pero las pruebas no son suficientes. Para casos de prueba, una fuente [69] utiliza 3009 y 884. Knuth sugirió 40902, 24140. Otro caso interesante son los dos números relativamente primos 14157 y 5950.
Pero es necesario identificar y comprobar los "casos excepcionales" [70] . ¿Funcionará correctamente "Poco elegante" cuando R > S, S > R, R = S? Lo mismo ocurre con "Elegante": ¿B > A, A > B, A = B? (Sí a todo). ¿Qué sucede cuando un número es cero y ambos números son cero? ("Poco elegante" se calcula siempre en todos los casos; "Elegante" se calcula siempre cuando A = 0.) ¿Qué sucede si se ingresan números negativos ? ¿Números fraccionarios? Si los números de entrada, es decir, el dominio de la función calculada por el algoritmo/programa, deben incluir sólo números enteros positivos incluido el cero, entonces las fallas en cero indican que el algoritmo (y el programa que lo instancia ) es una función parcial en lugar de una función total . Un fracaso notable por excepciones es el fallo del cohete Ariane 5 Vuelo 501 (4 de junio de 1996).
Prueba de la corrección del programa mediante el uso de inducción matemática : Knuth demuestra la aplicación de la inducción matemática a una versión "extendida" del algoritmo de Euclides y propone "un método general aplicable para demostrar la validez de cualquier algoritmo". [71] Tausworthe propone que una medida de la complejidad de un programa sea la duración de su prueba de corrección. [72]
Elegancia (compacidad) versus bondad (velocidad) : con sólo seis instrucciones básicas, "Elegante" es el claro ganador, en comparación con "Poco elegante" con trece instrucciones. Sin embargo, "Poco elegante" es más rápido (llega a HALT en menos pasos). El análisis de algoritmos [73] indica por qué es así: "Elegante" realiza dos pruebas condicionales en cada bucle de resta, mientras que "Poco elegante" sólo realiza una. Como el algoritmo (normalmente) requiere muchos bucles, en promedio se pierde mucho tiempo haciendo un "¿B = 0?" prueba que se necesita sólo después de calcular el resto.
¿Se pueden mejorar los algoritmos? : Una vez que el programador juzga que un programa es "adecuado" y "efectivo", es decir, calcula la función prevista por su autor, la pregunta es: ¿se puede mejorar?
La compacidad de "Inelegant" se puede mejorar eliminando cinco pasos. Pero Chaitin demostró que la compactación de un algoritmo no puede automatizarse mediante un algoritmo generalizado; [74] más bien, sólo puede hacerse de forma heurística ; es decir, mediante búsqueda exhaustiva (se pueden encontrar ejemplos en Busy beaver ), prueba y error, astucia, perspicacia, aplicación de razonamiento inductivo , etc. Observe que los pasos 4, 5 y 6 se repiten en los pasos 11, 12 y 13. Comparación con "Elegante" da una pista de que estos pasos, junto con los pasos 2 y 3, se pueden eliminar. Esto reduce el número de instrucciones básicas de trece a ocho, lo que lo hace "más elegante" que "Elegant", de nueve pasos.
La velocidad de "Elegant" se puede mejorar moviendo el botón "B=0?" prueba fuera de los dos bucles de resta. Este cambio requiere la adición de tres instrucciones (B = 0?, A = 0?, GOTO). Ahora "Elegante" calcula los números de ejemplo más rápido; Si este es siempre el caso para A, B y R, S dados, requeriría un análisis detallado.
Con frecuencia es importante saber qué cantidad de un recurso particular (como tiempo o almacenamiento) se requiere teóricamente para un algoritmo determinado. Se han desarrollado métodos para el análisis de algoritmos para obtener respuestas cuantitativas (estimaciones); por ejemplo, un algoritmo que suma los elementos de una lista de n números tendría un requisito de tiempo de , utilizando la notación O grande . En todo momento el algoritmo sólo necesita recordar dos valores: la suma de todos los elementos hasta el momento y su posición actual en la lista de entrada. Por lo tanto, se dice que tiene un requisito de espacio de , si no se cuenta el espacio requerido para almacenar los números de entrada, o si se cuenta.
Diferentes algoritmos pueden completar la misma tarea con un conjunto diferente de instrucciones en menos o más tiempo, espacio o " esfuerzo " que otros. Por ejemplo, un algoritmo de búsqueda binaria (con costo ) supera a una búsqueda secuencial (costo ) cuando se usa para búsquedas de tablas en listas o matrices ordenadas.
El análisis y estudio de algoritmos es una disciplina de la informática y, a menudo, se practica de forma abstracta sin el uso de un lenguaje o implementación de programación específica. En este sentido, el análisis de algoritmos se parece a otras disciplinas matemáticas en que se centra en las propiedades subyacentes del algoritmo y no en los detalles de una implementación en particular. Por lo general, se utiliza pseudocódigo para el análisis, ya que es la representación más simple y general. Sin embargo, en última instancia, la mayoría de los algoritmos generalmente se implementan en plataformas de hardware/software particulares y su eficiencia algorítmica eventualmente se pone a prueba utilizando código real. Para la solución de un problema "único", la eficiencia de un algoritmo particular puede no tener consecuencias significativas (a menos que n sea extremadamente grande), pero para algoritmos diseñados para un uso científico interactivo, comercial o de larga duración puede ser fundamental. Escalar de n pequeño a n grande frecuentemente expone algoritmos ineficientes que de otro modo serían benignos.
Las pruebas empíricas son útiles porque pueden descubrir interacciones inesperadas que afectan el rendimiento. Se pueden utilizar puntos de referencia para comparar antes/después de posibles mejoras en un algoritmo después de la optimización del programa. Sin embargo, las pruebas empíricas no pueden reemplazar el análisis formal y no es trivial realizarlas de manera justa. [75]
Para ilustrar las posibles mejoras posibles incluso en algoritmos bien establecidos, una importante innovación reciente, relacionada con los algoritmos FFT (muy utilizados en el campo del procesamiento de imágenes), puede reducir el tiempo de procesamiento hasta 1000 veces para aplicaciones como imágenes médicas. [76] En general, las mejoras de velocidad dependen de propiedades especiales del problema, que son muy comunes en aplicaciones prácticas. [77] Las aceleraciones de esta magnitud permiten que los dispositivos informáticos que hacen un uso extensivo del procesamiento de imágenes (como cámaras digitales y equipos médicos) consuman menos energía.
Hay varias formas de clasificar los algoritmos, cada una con sus propias ventajas.
Una forma de clasificar los algoritmos es mediante métodos de implementación.
Otra forma de clasificar los algoritmos es por su metodología o paradigma de diseño . Existe una cierta cantidad de paradigmas, cada uno diferente del otro. Además, cada una de estas categorías incluye muchos tipos diferentes de algoritmos. Algunos paradigmas comunes son:
Para problemas de optimización existe una clasificación de algoritmos más específica; un algoritmo para tales problemas puede caer en una o más de las categorías generales descritas anteriormente, así como en una de las siguientes:
Cada campo de la ciencia tiene sus propios problemas y necesita algoritmos eficientes. Los problemas relacionados en un campo a menudo se estudian juntos. Algunas clases de ejemplo son algoritmos de búsqueda , algoritmos de clasificación , algoritmos de fusión , algoritmos numéricos , algoritmos de gráficos , algoritmos de cadenas , algoritmos geométricos computacionales , algoritmos combinatorios , algoritmos médicos , aprendizaje automático , criptografía , algoritmos de compresión de datos y técnicas de análisis .
Los campos tienden a superponerse entre sí, y los avances algorítmicos en un campo pueden mejorar los de otros campos, a veces completamente sin relación. Por ejemplo, la programación dinámica se inventó para optimizar el consumo de recursos en la industria, pero ahora se utiliza para resolver una amplia gama de problemas en muchos campos.
Los algoritmos se pueden clasificar según la cantidad de tiempo que necesitan para completarse en comparación con su tamaño de entrada:
Algunos problemas pueden tener múltiples algoritmos de diferente complejidad, mientras que otros problemas pueden no tener algoritmos o no tener algoritmos eficientes conocidos. También hay asignaciones de algunos problemas a otros problemas. Debido a esto, se encontró que era más adecuado clasificar los problemas en sí en lugar de los algoritmos en clases de equivalencia basadas en la complejidad de los mejores algoritmos posibles para ellos.
El adjetivo "continuo" aplicado a la palabra "algoritmo" puede significar:
En programación lógica , se considera que los algoritmos tienen "un componente lógico, que especifica el conocimiento que se utilizará para resolver problemas, y un componente de control, que determina las estrategias de resolución de problemas mediante las cuales se utiliza ese conocimiento". [82]
El algoritmo euclidiano ilustra esta visión de un algoritmo. [83] [84] Aquí hay una representación de programación lógica, usando :- para representar "si", y la relación mcd(A, B, C) para representar la función mcd(A, B) = C:
mcd ( A , A , A ). mcd ( A , B , C ) : - A > B , mcd ( A - B , B , C ). mcd ( A , B , C ) : - B > A , mcd ( A , B - A , C ).En el lenguaje de programación lógica Ciao, la relación mcd se puede representar directamente en notación funcional:
mcd ( A , A ) := A . mcd ( A , B ) := mcd ( A - B , B ) :- A > B . mcd ( A , B ) := mcd ( A , B - A ) :- B > A .La implementación de Ciao traduce la notación funcional en una representación relacional en Prolog , extrayendo las restas incrustadas, AB y BA, como condiciones separadas:
mcd(A, A, A).mcd(A, B, C) :- A > B, A' es AB, mcd(A', B, C).mcd(A, B, C) :- B > A, B' es BA, mcd(A, B, C).El programa resultante tiene una lectura puramente lógica (y "declarativa" ), como una definición recursiva (o inductiva), que es independiente de cómo se utiliza la lógica para resolver problemas:
El mcd de A y A es A.El mcd de A y B es C, si A > B y A' es AB y el mcd de A' y B es C.El mcd de A y B es C, si B > A y B' es BA y el mcd de A y B' es C.Diferentes estrategias de resolución de problemas convierten la lógica en diferentes algoritmos. En teoría, dado un par de números enteros A y B, el razonamiento directo (o "de abajo hacia arriba") podría usarse para generar todos los casos de la relación mcd, terminando cuando se genera el mcd deseado de A y B. Por supuesto, el razonamiento directo es totalmente inútil en este caso. Pero en otros casos, como la definición de la secuencia de Fibonacci [82] y Datalog , el razonamiento directo puede ser una estrategia eficaz para la resolución de problemas. (Ver por ejemplo el programa lógico para calcular números de Fibonacci en Algoritmo = Lógica + Control ).
En contraste con la ineficiencia del razonamiento directo en este ejemplo, el razonamiento hacia atrás (o "de arriba hacia abajo") usando resolución SLD convierte la lógica en el algoritmo euclidiano:
Para encontrar el mcd C de dos números dados A y B:Si A = B, entonces C = A.Si A > B, entonces encuentre el mcd de AB y B, que es C.Si B > A, entonces encuentre el mcd de A y BA, que es C.Una de las ventajas de la representación de programación lógica del algoritmo es que su lectura puramente lógica hace que sea más fácil verificar que el algoritmo es correcto en relación con la definición estándar no recursiva de mcd. [83] Aquí está la definición estándar escrita en Prolog:
mcd ( A , B , C ) :- divide ( C , A ), divide ( C , B ), forall (( divide ( D , A ), divide ( D , B )), D =< C ). divide ( C , Número ) : - entre ( 1 , Número , C ), 0 es Número mod C.Esta definición, que es la especificación del algoritmo euclidiano, también es ejecutable en Prolog: el razonamiento hacia atrás trata la especificación como el algoritmo de fuerza bruta que itera a través de todos los números enteros C entre 1 y A, verificando si C divide a A y B. , y luego, para cada uno de ellos, C itera nuevamente a través de todos los números enteros D entre 1 y A, hasta que encuentra un C tal que C es mayor o igual a todos los D que también dividen A y B. Aunque este algoritmo es irremediablemente ineficiente, muestra que las especificaciones formales a menudo se pueden escribir en forma de programación lógica y pueden ser ejecutadas por Prolog, para comprobar que representan correctamente los requisitos informales .
Los algoritmos, por sí solos, no suelen ser patentables. En los Estados Unidos, una reivindicación que consiste únicamente en simples manipulaciones de conceptos, números o señales abstractos no constituye "procesos" (USPTO 2006), por lo que los algoritmos no son patentables (como en Gottschalk v. Benson ). Sin embargo, las aplicaciones prácticas de los algoritmos a veces son patentables. Por ejemplo, en Diamond v. Diehr , se consideró patentable la aplicación de un algoritmo de retroalimentación simple para ayudar en el curado del caucho sintético . Las patentes de software son controvertidas [85] y hay patentes criticadas que involucran algoritmos, especialmente algoritmos de compresión de datos , como la patente LZW de Unisys .
Además, algunos algoritmos criptográficos tienen restricciones de exportación (ver exportación de criptografía ).
La evidencia más antigua de algoritmos se encuentra en las matemáticas babilónicas de la antigua Mesopotamia (el actual Irak). Una tablilla de arcilla sumeria encontrada en Shuruppak , cerca de Bagdad , que data de c. 2500 aC describió el primer algoritmo de división . [11] Durante la dinastía Hammurabi c. 1800 – c. 1600 aC , tablillas de arcilla babilónicas describían algoritmos para calcular fórmulas . [86] Los algoritmos también se utilizaron en la astronomía babilónica . Las tablillas de arcilla babilónicas describen y emplean procedimientos algorítmicos para calcular la hora y el lugar de eventos astronómicos importantes. [87]
Los algoritmos para la aritmética también se encuentran en las matemáticas del antiguo Egipto , que se remontan al Papiro Matemático de Rhind c. 1550 a.C. [11] Los algoritmos se utilizaron más tarde en las matemáticas helenísticas antiguas . Dos ejemplos son el Tamiz de Eratóstenes , que fue descrito en la Introducción a la Aritmética por Nicómaco , [88] [14] : Capítulo 9.2 y el algoritmo euclidiano , que fue descrito por primera vez en los Elementos de Euclides ( c. 300 a. C. ). [14] : Capítulo 9.1
Marcas de conteo: Para realizar un seguimiento de sus rebaños, sus sacos de grano y su dinero, los antiguos utilizaban el conteo: acumulando piedras o marcas rayadas en palos o haciendo símbolos discretos en arcilla. A través del uso babilónico y egipcio de marcas y símbolos, eventualmente evolucionaron los números romanos y el ábaco (Dilson, p. 16-41). Las marcas de conteo aparecen de manera prominente en la aritmética del sistema numérico unario utilizado en los cálculos de la máquina de Turing y Post-Turing .
Muhammad ibn Mūsā al-Khwārizmī , un matemático persa , escribió el Al-jabr en el siglo IX. Los términos " algorismo " y "algoritmo" se derivan del nombre al-Khwārizmī, mientras que el término " álgebra " se deriva del libro Al-jabr . En Europa, la palabra "algoritmo" se utilizó originalmente para referirse a los conjuntos de reglas y técnicas utilizadas por Al-Khwarizmi para resolver ecuaciones algebraicas, antes de generalizarse para referirse a cualquier conjunto de reglas o técnicas. [89] Esto finalmente culminó en la noción de Leibniz del cálculo razonador ( c. 1680 ):
Un buen siglo y medio adelantado a su tiempo, Leibniz propuso un álgebra de la lógica, un álgebra que especificaría las reglas para manipular conceptos lógicos de la misma manera que el álgebra ordinaria especifica las reglas para manipular números. [90]
El primer algoritmo criptográfico para descifrar códigos cifrados fue desarrollado por Al-Kindi , un matemático árabe del siglo IX , en Un manuscrito sobre el descifrado de mensajes criptográficos . Dio la primera descripción del criptoanálisis mediante análisis de frecuencia , el primer algoritmo de descifrado de códigos . [15]
El reloj : Bolter acredita la invención del reloj impulsado por pesas como "La invención clave [de Europa en la Edad Media]", en particular, el escape de borde [91] que nos proporciona el tic y tac de un reloj mecánico. "La máquina automática precisa" [92] condujo inmediatamente a los " autómatas mecánicos " a partir del siglo XIII y finalmente a las "máquinas computacionales": la máquina diferenciadora y las máquinas analíticas de Charles Babbage y la condesa Ada Lovelace , a mediados del siglo XIX. [93] A Lovelace se le atribuye la primera creación de un algoritmo destinado al procesamiento en una computadora (el motor analítico de Babbage, el primer dispositivo considerado una verdadera computadora completa de Turing en lugar de solo una calculadora ) y a veces se le llama "el primer programador de la historia" como un resultado, aunque la implementación completa del segundo dispositivo de Babbage no se realizaría hasta décadas después de su vida.
Máquinas lógicas 1870 - "Ábaco lógico" y "máquina lógica" de Stanley Jevons : el problema técnico era reducir las ecuaciones booleanas cuando se presentaban en una forma similar a lo que ahora se conoce como mapas de Karnaugh . Jevons (1880) describe primero un simple "ábaco" de "piezas de madera provistas de alfileres, diseñadas para que cualquier parte o clase de las combinaciones [lógicas] pueda seleccionarse mecánicamente... Más recientemente, sin embargo, he reducido el sistema a una forma completamente mecánica, y así han incorporado todo el proceso indirecto de inferencia en lo que podría llamarse una Máquina Lógica ". Su máquina venía equipada con "ciertas varillas de madera móviles" y "al pie hay 21 llaves como las de un piano [etc.]...". Con esta máquina podía analizar un " silogismo o cualquier otro argumento lógico simple". [94]
Esta máquina la exhibió en 1870 ante los miembros de la Royal Society. [95] Otro lógico, John Venn , sin embargo, en su Lógica simbólica de 1881 , miró con ictericia este esfuerzo: "Yo mismo no tengo una alta estimación del interés o la importancia de lo que a veces se llama máquinas lógicas... no parece "Todos los inventos actualmente conocidos o que probablemente se descubran merecen realmente el nombre de máquinas lógicas"; ver más en Caracterizaciones de algoritmos . Pero para no quedarse atrás, él también presentó "un plan un tanto análogo, entiendo, al ábaco del Prof. Jevon ... [Y] [una] vez más, correspondiente a la máquina lógica del Prof. Jevons, se puede describir el siguiente dispositivo. Prefiero llamarla simplemente una máquina de diagramas lógicos... pero supongo que podría hacer completamente todo lo que racionalmente se puede esperar de cualquier máquina lógica". [96]
Telar de Jacquard, tarjetas perforadas Hollerith, telegrafía y telefonía: el relé electromecánico : Bell y Newell (1971) indican que el telar de Jacquard (1801), precursor de las tarjetas Hollerith (tarjetas perforadas, 1887), y las "tecnologías de conmutación telefónica" fueron las raíces. de un árbol que condujo al desarrollo de las primeras computadoras. [97] A mediados del siglo XIX, el telégrafo , el precursor del teléfono, se utilizaba en todo el mundo, y su codificación discreta y distinguible de letras como "puntos y rayas" era un sonido común. A finales del siglo XIX, el teletipo ( c. 1870 ) estaba en uso, al igual que el uso de tarjetas Hollerith en el censo estadounidense de 1890. Luego vino la teleimpresora ( c. 1910 ) con su uso en papel perforado del código Baudot en cinta.
Las redes de conmutación telefónica de relés electromecánicos (inventadas en 1835) fueron obra de George Stibitz (1937), el inventor del dispositivo sumador digital. Mientras trabajaba en los Laboratorios Bell, observó el uso "gravoso" de calculadoras mecánicas con engranajes. "Volvió a casa una noche de 1937 con la intención de probar su idea... Cuando terminaron los retoques, Stibitz había construido un dispositivo de suma binaria". [98 ]
El matemático Martin Davis observa la particular importancia del relé electromecánico (con sus dos "estados binarios" abierto y cerrado ):
Símbolos y reglas : En rápida sucesión, las matemáticas de George Boole (1847, 1854), Gottlob Frege (1879) y Giuseppe Peano (1888-1889) redujeron la aritmética a una secuencia de símbolos manipulados por reglas. Los principios de la aritmética, presentados mediante un nuevo método (1888) de Peano fueron "el primer intento de axiomatización de las matemáticas en un lenguaje simbólico ". [100]
Pero Heijenoort felicita a Frege (1879): la de Frege es "quizás la obra más importante jamás escrita en lógica... en la que vemos un " 'lenguaje de fórmulas', es decir, una lingua caracterica , un lenguaje escrito con símbolos especiales. , "para el pensamiento puro", es decir, libre de adornos retóricos... construidos a partir de símbolos específicos que se manipulan según reglas definidas". [101] El trabajo de Frege fue simplificado y amplificado aún más por Alfred North Whitehead y Bertrand Russell en sus Principia Mathematica (1910-1913).
Las paradojas : Al mismo tiempo, aparecieron en la literatura una serie de paradojas inquietantes, en particular, la paradoja de Burali-Forti (1897), la paradoja de Russell (1902-03) y la paradoja de Richard . [102] Las consideraciones resultantes llevaron al artículo de Kurt Gödel (1931) (cita específicamente la paradoja del mentiroso) que reduce completamente las reglas de recursividad a números.
Calculabilidad efectiva : En un esfuerzo por resolver el Entscheidungsproblem definido precisamente por Hilbert en 1928, los matemáticos se propusieron por primera vez definir qué se entendía por "método efectivo" o "cálculo efectivo" o "calculabilidad efectiva" (es decir, un cálculo que tendría éxito ). En rápida sucesión aparecieron los siguientes: El cálculo λ de Alonzo Church , Stephen Kleene y JB Rosser [103], una definición finamente perfeccionada de "recursión general" a partir del trabajo de Gödel, que actúa según las sugerencias de Jacques Herbrand (cf. las conferencias de Gödel en Princeton sobre 1934) y simplificaciones posteriores de Kleene. [104] La prueba de Church [105] de que el Entscheidungsproblem era irresoluble, la definición de Emil Post de calculabilidad efectiva como un trabajador que sigue sin pensar una lista de instrucciones para moverse hacia la izquierda o hacia la derecha a través de una secuencia de habitaciones y, mientras está allí, marcar o borrar un papel. u observe el documento y tome una decisión de sí o no sobre la siguiente instrucción. [106] La prueba de Alan Turing de que el Entscheidungsproblem no tenía solución mediante el uso de su "máquina [automática]" [107] —en efecto, casi idéntica a la "formulación" de Post, la definición de "método eficaz" de J. Barkley Rosser " en términos de "una máquina". [108] La propuesta de Kleene de un precursor de la " tesis de la Iglesia " que llamó "Tesis I", [109] y unos años más tarde, Kleene cambió el nombre de su tesis a "Tesis de la Iglesia" [110] y propuso la "Tesis de Turing". [111]
Emil Post (1936) describió las acciones de una "computadora" (ser humano) de la siguiente manera:
Su espacio simbólico sería
El trabajo de Alan Turing [113] precedió al de Stibitz (1937); Se desconoce si Stibitz conocía la obra de Turing. El biógrafo de Turing creía que el uso por parte de Turing de un modelo parecido a una máquina de escribir derivaba de un interés juvenil: "Alan había soñado con inventar máquinas de escribir cuando era niño; la señora Turing tenía una máquina de escribir, y bien podría haber comenzado preguntándose qué significaba llamar una máquina de escribir 'mecánica ' ". [114] Dada la prevalencia en ese momento del código Morse, la telegrafía, las máquinas de teletipo y los teletipos, es muy posible que todos fueran influencias en Turing durante su juventud.
Turing (su modelo de computación ahora se llama máquina de Turing) comienza, al igual que Post, con un análisis de una computadora humana que reduce a un simple conjunto de movimientos básicos y "estados mentales". Pero va un paso más allá y crea una máquina como modelo de cálculo de números. [115]
La reducción de Turing produce lo siguiente:
"Puede ser que algunos de estos cambios invoquen necesariamente un cambio de estado de ánimo. Por lo tanto, debe considerarse que la operación más general es una de las siguientes:
Unos años más tarde, Turing amplió su análisis (tesis, definición) con esta contundente expresión del mismo:
J. Barkley Rosser definió un "método [matemático] eficaz" de la siguiente manera (cursiva agregada):
La nota a pie de página número 5 de Rosser hace referencia al trabajo de (1) Church y Kleene y su definición de λ-definibilidad, en particular, el uso que hace Church de ella en su An Unsolvable Problem of Elementary Number Theory (1936); (2) Herbrand y Gödel y su uso de la recursividad, en particular, el uso de Gödel en su famoso artículo Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I (1931); y (3) Post (1936) y Turing (1936-37) en sus modelos de mecanismo de computación.
Stephen C. Kleene definió su ahora famosa "Tesis I" conocida como la tesis de Church-Turing . Pero lo hizo en el siguiente contexto (en negrita en el original):
Se han dirigido varios esfuerzos hacia un mayor refinamiento de la definición de "algoritmo", y la actividad continúa debido a cuestiones relacionadas, en particular, con los fundamentos de las matemáticas (especialmente la tesis de Church-Turing ) y la filosofía de la mente (especialmente los argumentos sobre inteligencia artificial ). Para obtener más información, consulte Caracterizaciones de algoritmos .
Sin embargo, quiere un nuevo algoritmo, un método completo mediante el cual se puedan establecer los teoremas sin ambigüedades ni circunloquios, [...]
[...] siguiente nivel de abstracción de la burocracia central: algoritmos que operan globalmente.
Un algoritmo es una receta, método o técnica para hacer algo.
Este artículo incorpora material de dominio público de Paul E. Black. "algoritmo". Diccionario de Algoritmos y Estructuras de Datos . NIST .
{{cite book}}: |journal=ignorado ( ayuda ){{cite book}}: |journal=ignorado ( ayuda ) , ISBN 0-671-49207-1 . Cfr. Capítulo "El Espíritu de la Verdad" para una historia que conduce a su prueba y una discusión sobre ella. 
