En matemáticas e informática , las máquinas Zeno (abreviado ZM , y también llamado máquina de Turing acelerada , 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 de pasos algorítmicos. [1] Estas máquinas están descartadas en la mayoría de los modelos de cálculo.
La idea de las máquinas Zeno fue discutida por primera vez por Hermann Weyl en 1927; el nombre se refiere a las paradojas de Zenón , atribuidas al antiguo filósofo griego Zenón de Elea . Las máquinas Zeno juegan 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 Zeno son posibles.
Definición
Una máquina 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 se toman unidades de tiempo para realizar la -th paso; así, 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.
Máquinas de Turing del tiempo infinito
Un modelo más formal de la máquina Zeno es la máquina de Turing de tiempo infinito . Definido primero en un trabajo inédito de Jeffrey Kidder y ampliado 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 la máquina de Turing, para incluir el tiempo transfinito ; ese es 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 de inicio, con una cinta vacía, cabecera de lectura en la celda 0) y un procedimiento para pasar de un estado al estado sucesivo. De esta forma se define el estado de una máquina de Turing para todos los pasos correspondientes a un número natural. Un ITTM mantiene estas propiedades, pero también define el estado de la máquina en ordinales límite , es decir, ordinales que no son nini el sucesor de ningún ordinal. El estado de una máquina de Turing consta de 3 partes:
- El estado
- La ubicación del cabezal de lectura y escritura.
- El contenido de la cinta
Así como una máquina de Turing clásica tiene un estado de inicio etiquetado, que es el estado al comienzo de un programa, un 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 cualquier paso de límite. [1] [2] Por último, el estado de la cinta está determinado por el límite superior de los estados anteriores de la cinta. Para alguna maquina, Una célula y, un límite ordinal luego
Eso es el th celda a la vez es el límite superior de esa misma celda cuando la máquina se acerca . [1] Esto se puede considerar como el límite si converge ode lo contrario. [1]
Computabilidad
Las máquinas Zeno se han propuesto como un modelo de computación más poderoso que las máquinas clásicas de Turing, basándose en su capacidad para resolver el problema de la detención de las máquinas clásicas de Turing. [3] Cristian Calude y Ludwig Staiger presentan el siguiente algoritmo de pseudocódigo como una solución al problema de detención cuando se ejecuta en una máquina Zeno. [4]
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, entonces escriba 1 en la primera posición de la cinta de salida y salga del bucle; final del ciclo final del programa
Inspeccionando la primera posición de la cinta de salida después unidad de tiempo transcurrido, podemos determinar si la máquina de Turing dada se detiene. [4] En contraste, Oron Shagir sostiene que el estado de una máquina Zeno solo se define en el intervalo, por lo que es imposible inspeccionar la cinta en el momento . Además, dado que las máquinas clásicas de Turing no tienen ninguna información de tiempo, la adición de información de tiempo, ya sea que se acelere o no, no agrega ningún poder computacional. [3]
Sin embargo, las máquinas de Turing de tiempo infinito son capaces de implementar el algoritmo dado, deteniéndose en el tiempo con la solución correcta, [2] ya que definen su estado para pasos transfinitos. [3] TodosLos conjuntos son decidibles por máquinas de Turing de tiempo infinito, ylos conjuntos son semidecidibles . [2] [ aclaración necesaria ]
Las máquinas Zeno no pueden resolver su propio problema de detención. [4]
Ver también
Referencias
- ↑ a b c d e Hamkins, Joel (3 de diciembre de 2002). "Máquinas de Turing del tiempo infinito". arXiv : matemáticas / 0212047 .
- ^ a b c d e Hamkins, Joel; Lewis, Andy (21 de agosto de 1998). "Máquinas de Turing del tiempo infinito". arXiv : matemáticas / 9808093 .
- ^ a b c Shagir, Oron, Super-Tasks, Accelerating Turing Machines and Uncomputability (PDF) , archivado desde el original (PDF) el 9 de julio de 2007
- ^ a b c Calude, Cristian; Staiger, Ludwig, Una nota sobre las máquinas de Turing aceleradas (PDF)