Editando Algoritmo (sección)

== Definición ==
En general, no existe ningún consenso definitivo en cuanto a la definición formal de algoritmo. Muchos autores los señalan como listas de instrucciones para resolver un [[cálculo]] o un [[problema abstracto]], es decir, que un número finito de pasos convierten los datos de un problema (entrada) en una solución (salida).<ref name="Brassard" /><ref name="rae"/><ref name="Cormen">{{Cita libro |apellidos=Cormen |nombre=Thomas |enlaceautor=Thomas H. Cormen |título=Introduction to algorithms |año=2009 |editorial=Cambridge, Massachusetts: The [[MIT Press]] |isbn = 978-0-262-53305-8|apellidos2=Leiserson, Charles |apellidos3=Rivest, Ronald |apellidos4=Stein, Clifford}}</ref><ref name="Grimaldi">{{Cita libro |apellidos=Ralph P. Grimaldi |título=Matemáticas Discreta y Combinatoria |año=1998 |editorial=México: Addison Wesley Longman de México |capítulo=Propiedades de los números enteros: Inducción matemática |isbn = 968-444-324-2}}</ref><ref name="Johnsonbaugh">{{Cita libro |apellidos=Johnsonbaugh, Richard |título=Matemáticas Discretas |año=2005 |editorial=México: PEARSON EDUCACIÓN |capítulo=Introducción a la teoría de números |isbn = 970-26-0637-3}}</ref><ref name="Reynolds">{{Cita libro |apellidos=Carl Reynolds & Paul Tymann |título=Schaum's Outline of Principles of Computer Science |año=2008 |editorial=McGraw-Hill |isbn = 978-0-07-146051-4}}</ref> Sin embargo, cabe notar que algunos algoritmos no tienen necesariamente que terminar o resolver un problema en particular. Por ejemplo, una versión modificada de la [[criba de Eratóstenes]], que nunca termine de calcular números primos, no deja de ser un algoritmo.<ref name="Gurevich">{{Cita publicación |url=http://research.microsoft.com/en-us/um/people/gurevich/Opera/141.pdf |título=Sequential Abstract State Machines capture Sequential Algorithms |apellidos=Gurevich, Yuri |volumen=1 |número=1 |páginas=77-111 |issn=1529-3785 |año=2000 |revista=ACM Transactions on Computational Logic}}</ref>

A lo largo de la historia, varios autores han tratado de definir formalmente los algoritmos utilizando modelos matemáticos. Esto lo hizo [[Alonzo Church]] en 1936 con el concepto de «calculabilidad efectiva» basada en su [[cálculo lambda]] y por [[Alan Turing]] basándose en la [[máquina de Turing]]. Los dos enfoques son equivalentes, en el sentido de que se pueden resolver exactamente los mismos problemas con ambos enfoques.<ref name="savage">{{Cita libro |apellidos=John E. Savage |título=The Complexity of Computing |año=1987 |editorial=Krieger Publishing Co. |isbn=089874833X}}</ref><ref name="sipser">{{Cita libro |apellidos=Sipser |nombre=Michael |título=Introduction to the Theory of Computation |url=http://www-math.mit.edu/~sipser/ |año=2005 |editorial=Course Technology |isbn=978-0534950972 |edición=2 |urlarchivo=https://web.archive.org/web/20060615070738/http://www-math.mit.edu/~sipser/ |fechaarchivo=15 de junio de 2006}}</ref> No obstante, estos modelos están sujetos a un tipo particular de datos, como son números, símbolos o [[Grafo|gráficas]] mientras que, en general, los algoritmos funcionan sobre una vasta cantidad de [[Estructura de datos|estructuras de datos]].<ref name="Cormen" /><ref name="Brassard" /> En general, la parte común en todas las definiciones se puede resumir en las siguientes tres propiedades, siempre y cuando no consideremos [[Algoritmo paralelo|algoritmos paralelos]]:<ref name="Gurevich" />
* Tiempo secuencial. Un algoritmo funciona en tiempo discretizado –paso a paso–, definiendo así una secuencia de estados ''computacionales'' por cada entrada válida (la ''entrada'' son los datos que se le suministran al algoritmo antes de comenzar).
* Estado abstracto. Cada estado computacional puede ser descrito formalmente utilizando una [[Lógica matemática|estructura de primer orden]] y cada algoritmo es independiente de su implementación (los algoritmos son objetos abstractos), de manera que en un algoritmo las estructuras de primer orden son invariantes bajo isomorfismo.
* Exploración acotada. La transición de un estado al siguiente queda completamente determinada por una descripción fija y finita; es decir, entre cada estado y el siguiente solamente se puede tomar en cuenta una cantidad fija y limitada de términos del estado actual.

En resumen, un algoritmo es cualquier cosa que funcione paso a paso, donde cada paso se pueda describir sin ambigüedad y sin hacer referencia a una computadora en particular, y además tiene un límite fijo en cuanto a la cantidad de datos que se pueden leer/escribir en un solo paso.<ref>{{Cita publicación|url=https://www.sciencedirect.com/science/article/pii/S2215016124002863|título=A methodological approach for enhancing visualization of country data representation in the presence of significant spatial disparity|apellidos=Fleta-Asín, J.; Muñoz, F; Sáenz-Royo, C.|fecha=3-7-2024|publicación=MethodsX|doi=10.1016/j.mex.2024.102833| issn = 2215-0161}}</ref>

Esta amplia definición abarca tanto a algoritmos prácticos como aquellos que solo funcionan en teoría, por ejemplo, el [[método de Newton]] y la [[eliminación de Gauss-Jordan]] funcionan, al menos en principio, con números de precisión infinita; sin embargo, no es posible programar la precisión infinita en una computadora, y no por ello dejan de ser algoritmos.<ref name="Dershowitz">{{Cita publicación |url=http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf |título=A natural axiomatization of computability and proof of Church's Thesis |apellidos=Nachum Dershowitz & Yuri Gurevich |volumen=14 |número=3 |páginas=299-350 |issn=1079-8986 |año=2008 |revista=Bulletin of Symbolic Logic}}</ref> En particular es posible considerar una cuarta propiedad que puede usarse para validar la [[tesis de Church-Turing]], de que toda función calculable se puede programar en una máquina de Turing (o equivalentemente, en un lenguaje de programación suficientemente general):<ref name="Dershowitz" />
* Aritmetizabilidad. Solamente operaciones innegablemente calculables están disponibles en el paso inicial.