¿Qué es un algoritmo? ¿Es simplemente una máquina de Turing? Si no, ¿qué es?

Un algoritmo es una secuencia de pasos finita y ejecutable que calcula una función .

Los algoritmos son finitos tanto en términos del número total de pasos en la especificación del algoritmo (piense en el código fuente) como en términos del número de pasos ejecutados cuando se ejecuta el algoritmo. Es decir, si los pasos se repiten (a través de saltos a un paso anterior, para bucles, mientras que bucles, etc.), nunca entran en un bucle infinito.

Todos los pasos son ejecutables , lo que significa que se reducen a algún tipo de manipulación / transformación simbólica inequívoca. Un ejemplo de un paso ejecutable es: “agregar dos variables con valores enteros x e y”. Un ejemplo de un paso no ejecutable es: “adivina mágicamente la salida de alguna función dada alguna entrada”.

Una función es un mapeo entre elementos de algún conjunto de entrada (el dominio de la función) y un conjunto de salida (el rango de la función), de modo que cada elemento en el dominio se mapea a uno y solo un elemento en el rango.

Cualquier máquina de Turing puede implementar cualquier algoritmo, y cualquier máquina de Turing que nunca entre en un bucle infinito implementa un algoritmo.

“Algoritmo” es el concepto más general. Una máquina de Turing es una de las muchas formalizaciones que es un algoritmo.

Supongo que ya sabes lo que es una máquina de Turing. Un algoritmo es simplemente cualquier forma de descripción de cómo manipular la entrada para producir salida. Los diagramas de flujo también serían ejemplos de algoritmos, además de las máquinas de Turing.

Hay una simplificación que estoy haciendo. Para que una descripción califique formalmente como un “algoritmo”, una definición común exigiría que cualquier entrada produjera salida en un número finito de pasos. Esto significaría que algunos TM: s en realidad no calificarían como algoritmos. Y en realidad no hay una forma segura de determinar qué TM: s son algoritmos; consulte “El problema de detención”.