En matemáticas y ciencias de la computación , las máquinas de Zenón (abreviadas ZM , y también llamadas máquinas de Turing aceleradas , ATM ) son un modelo computacional hipotético relacionado con las máquinas de Turing que son capaces de realizar cálculos que involucran un número infinito contable de pasos algorítmicos. [1] Estas máquinas están descartadas en la mayoría de los modelos de computación.
La idea de las máquinas de Zenón fue discutida 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 Zenón es una máquina de Turing que puede realizar una cantidad infinita de pasos y luego continuar realizando más pasos. Esto puede considerarse como una supertarea en la que se toman unidades de tiempo para realizar el paso -ésimo; 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 una cantidad infinita de pasos.
Un modelo más formal de la máquina de Zenón 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 (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 estado sucesivo. De esta manera, 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, los ordinales que no son ni el sucesor de ningún ordinal. El estado de una máquina de Turing consta de 3 partes:
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] Este es el caso incluso si la máquina no tiene otra forma de acceder a este estado, por ejemplo, ningún nodo pasa a él. La ubicación del cabezal de lectura y escritura se establece en cero para en cualquier paso límite. [1] [2] Por último, el estado de la cinta está determinado por el límite supremo de los estados de cinta anteriores. Para alguna máquina , una celda y, un ordinal límite entonces
Es decir, la celda n en ese momento es el límite supremo de esa misma celda a medida que la máquina se acerca a . [1] Esto puede considerarse como el límite si converge o no. [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 detención de las máquinas de Turing clásicas. [3] Cristian Calude y Ludwig Staiger presentan el siguiente algoritmo de pseudocódigo como solución al problema de detención cuando se ejecuta en una máquina Zeno. [4]
Iniciar programa escribe 0 en la primera posición de la cinta de salida; iniciar 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 entonces escribe 1 en la primera posición de la cinta de salida y rompe el bucle; Fin del ciclo Fin del programa
Al inspeccionar la primera posición de la cinta de salida después de que haya transcurrido una unidad de tiempo, podemos determinar si la máquina de Turing dada se detiene. [4] Por el contrario, Oron Shagrir sostiene que el estado de una máquina de Zeno solo está definido en el intervalo , por lo que es imposible inspeccionar la cinta en el tiempo . Además, dado que las máquinas de Turing clásicas no tienen ninguna información de tiempo, la adición de información de tiempo, ya sea que acelere 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 momento en que se obtiene la solución correcta, [2] ya que definen su estado para pasos transfinitos. [3] Todos los conjuntos son decidibles por las máquinas de Turing de tiempo infinito, y los conjuntos son semidecidibles . [2] [ aclaración necesaria ]
Las máquinas de Zenón no pueden resolver su propio problema de detención. [4]
