Máquina de Zenón , la enciclopedia libre

En matemáticas y ciencias de la computación, las máquinas de Zenón (también llamadas máquinas aceleradas de Turing)^[1]​ son un modelo computacional hipotético relacionado con la máquina de Turing que permite realizar un número conjunto numerable de pasos algorítmicos en tiempo finito. Estas máquinas están descartadas en la mayoría de los modelos de computación.^[2]​

Más formalmente, una máquina de Zenón es una máquina de Turing que requiere 2⁻ⁿ unidades de tiempo para realizar su n-ésimo paso; por lo tanto, el primer paso requiere 0.5 unidades de tiempo, el segundo 0.25, el tercero 0.125 y así sucesivamente, de modo que después de una unidad de tiempo, se habrá realizado un número de pasos conjunto numerable (es decir, ℵ₀).

La idea de las máquinas de Zenón fue discutida por primera vez por Hermann Weyl en 1927; el nombre se refiere a las paradojas de Zenón, atribuidas al filósofo griego Zenón de Elea. Las máquinas de Zenón desempeñan un papel crucial en algunas teorías. La teoría del punto omega ideada por el físico Frank J. Tipler, por ejemplo, solo puede ser válida si las máquinas Zenón son posibles.

Las máquinas de Zenón permitirían que se computaran algunas funciones que no son computables mediante máquinas de Turing. Por ejemplo, el problema de la parada para las máquinas de Turing se puede resolver con una máquina de Zenón (utilizando el siguiente algoritmo escrito en pseudocódigo):

comenzar el programa escriba 0 en la primera posición de la cinta de salida; comenzar bucle   simular 1 paso sucesivo de la máquina de Turing dada en la entrada dada;   si la máquina de Turing se ha detenido, escriba 1 en la primera posición de la cinta de salida y rompa el ciclo; bucle final programa final 

El cálculo de este tipo que va más allá del límite de Turing se denomina hipercomputación, en este caso, hipercomputación a través de una supertarea.

• Hipercomputación
• Paradoja de Ross-Littlewood
• Supertarea
• Lámpara de Thomson
• Punto Omega de Tipler
• Paradojas de Zenón

• Petrus H. Potgieter, Zeno machines and hypercomputation, 2006.