Máquina de Zenón

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.

Máquinas de Zenón y computabilidad

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.

Véase también

Enlaces externos

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

Referencias

↑ Hector Zenil (2013). A Computable Universe: Understanding and Exploring Nature as Computation. World Scientific. pp. 542 de 810. ISBN 9789814374309. Consultado el 16 de abril de 2019.
↑ Cris Calude, Gheorghe Paun (2000). Computing with Cells and Atoms: An Introduction to Quantum, DNA and Membrane Computing. CRC Press. pp. 206 de 320. ISBN 9780748408993. Consultado el 14 de abril de 2019.

Datos: Q2072061

[ZENIL-1] Hector Zenil (2013). A Computable Universe: Understanding and Exploring Nature as Computation. World Scientific. pp. 542 de 810. ISBN 9789814374309. Consultado el 16 de abril de 2019.

[PAUN-2] Cris Calude, Gheorghe Paun (2000). Computing with Cells and Atoms: An Introduction to Quantum, DNA and Membrane Computing. CRC Press. pp. 206 de 320. ISBN 9780748408993. Consultado el 14 de abril de 2019.

[1]

[2]