Máquina Zeno

En matemáticas e informática , las máquinas de Zeno (abreviadas ZM , también llamadas máquinas de Turing aceleradas , ATM ) son un modelo computacional hipotético relacionado con las máquinas de Turing , capaz de realizar cálculos que implican un número infinito numerable de pasos algorítmicos. ^{[ 1 ]} Estas máquinas se excluyen en la mayoría de los modelos de computación.

La idea de las máquinas de Zenón fue planteada por primera vez por Hermann Weyl en 1927; el nombre hace referencia a las paradojas de Zenón , atribuidas al antiguo 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 de Zenón son posibles.

Una máquina de Zeno es una máquina de Turing que puede dar un número infinito de pasos y luego continuar dando más pasos. Esto puede pensarse como una supertarea donde${\displaystyle {\frac {1}{2^{n}}}}$Se necesitan unidades de tiempo para realizar la${\displaystyle n}$-ésimo paso; por lo tanto, el primer paso toma 0,5 unidades de tiempo, el segundo toma 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 infinito numerable de pasos.

Un modelo más formal de la máquina de Zeno es la máquina de Turing de tiempo infinito . Definida por primera vez en un trabajo inédito de Jeffrey Kidder y ampliada por Joel Hamkins y Andy Lewis en Infinite Time Turing Machines , ^{[ 2 ]} la máquina de Turing de tiempo infinito es una extensión del modelo clásico de máquina de Turing para incluir el tiempo transfinito ; es decir, el tiempo más allá de todo tiempo finito. ^{[ 2 ]} Una máquina de Turing clásica tiene un estado en el paso${\displaystyle 0}$(en el estado inicial, con una cinta vacía, cabezal de lectura en la celda 0) y un procedimiento para pasar de un estado al siguiente. De esta forma, el estado de una máquina de Turing se define para todos los pasos correspondientes a un número natural. Una ITTM mantiene estas propiedades, pero también define el estado de la máquina en los ordinales límite , es decir, ordinales que no son ni${\displaystyle 0}$ni el sucesor de ningún ordinal. El estado de una máquina de Turing consta de 3 partes:

1. El estado
2. La ubicación del cabezal de lectura/escritura
3. El contenido de la cinta

Así como una máquina de Turing clásica tiene un estado inicial etiquetado, que es el estado al comienzo de un programa, una ITTM tiene un estado límite etiquetado , que es el estado de la máquina en cualquier ordinal límite. ^{[ 1 ]} Esto es así incluso si la máquina no tiene otra forma de acceder a este estado, por ejemplo, ningún nodo realiza transiciones a él. La ubicación del cabezal de lectura/escritura se establece en cero para cualquier paso límite. ^{[ 1 ] [ 2 ]} Por último, el estado de la cinta está determinado por el supremo límite de los estados de cinta anteriores. Para alguna máquina${\displaystyle T}$, una célula${\displaystyle k}$y, un ordinal límite${\displaystyle \lambda }$entonces

${\displaystyle T(\lambda )_{k}=\limsup _{n\rightarrow \lambda }T(n)_{k}}$

Esa es la${\displaystyle k}$la célula en el momento${\displaystyle \lambda }$es el límite supremo de esa misma celda a medida que la máquina se acerca${\displaystyle \lambda }$. ^{[ 1 ]} Esto puede pensarse como el límite si converge o${\displaystyle 1}$de lo contrario. ^{[ 1 ]}

Las máquinas Zeno se han propuesto como un modelo de computación más potente que las máquinas de Turing clásicas, basándose en su capacidad para resolver el problema de la parada para las máquinas de Turing clásicas. ^{[ 3 ]} Cristian Calude y Ludwig Staiger presentan el siguiente algoritmo en pseudocódigo como solución al problema de la parada cuando se ejecuta en una máquina Zeno. ^{[ 4 ]}

comenzar programa escribir 0 en la primera posición de la cinta de salida; comenzar bucle simular 1 paso sucesivo de la máquina de Turing dada con la entrada dada; Si la máquina de Turing se ha detenido, entonces escribe 1 en la primera posición de la cinta de salida y sal del bucle; Fin del bucle Fin del programa

Al inspeccionar la primera posición de la cinta de salida después${\displaystyle 1}$Una vez transcurrida una unidad de tiempo, podemos determinar si la máquina de Turing dada se detiene. ^{[ 4 ]} En contraste, Oron Shagrir argumenta que el estado de una máquina de Zeno solo se define en el intervalo${\displaystyle [0,1)}$y por lo tanto es imposible inspeccionar la cinta en ese momento.${\displaystyle 1}$. Además, dado que las máquinas de Turing clásicas no tienen información de temporización, la adición de información de temporización, ya sea acelerando o no, no agrega en sí misma ninguna potencia computacional. ^{[ 3 ]}

Sin embargo, las máquinas de Turing de tiempo infinito son capaces de implementar el algoritmo dado, deteniéndose en el tiempo${\displaystyle \omega }$con la solución correcta, ^{[ 2 ]} ya que definen su estado para pasos transfinitos. ^{[ 3 ]} Todos${\displaystyle \Pi _{1}^{1}}$Los conjuntos son decidibles por máquinas de Turing de tiempo infinito, y${\displaystyle \Delta _ {2}^{1}}$Los conjuntos son semidecidibles . ^{[ 2 ]}

Las máquinas de Zeno no pueden resolver su propio problema de parada. ^{[ 4 ]}

• Cálculo en el límite
• Secuencia de especímenes
• paradoja de Ross-Littlewood