Enmatemáticas yciencias de la computación, lasmáquinas de Zenón (también llamadasmáquinas aceleradas de Turing)[1] son unmodelo computacional hipotético relacionado con lamáquina de Turing que permite realizar un númeroconjunto 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−n unidades de tiempo para realizar sun-é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 pasosconjunto numerable (es decir,ℵ0).
La idea de las máquinas de Zenón fue discutida por primera vez porHermann Weyl en 1927; el nombre se refiere a lasparadojas de Zenón, atribuidas alfilósofo griegoZenón de Elea. Las máquinas de Zenón desempeñan un papel crucial en algunas teorías. La teoría delpunto omega ideada por el físicoFrank 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, elproblema de la parada para las máquinas de Turing se puede resolver con una máquina de Zenón (utilizando el siguiente algoritmo escrito enpseudocódigo):
comenzar el programaescriba 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 finalprograma final
El cálculo de este tipo que va más allá del límite de Turing se denominahipercomputación, en este caso, hipercomputación a través de unasupertarea.
| Control de autoridades |
|
|---|
Datos:Q2072061