El infinitary la computabilidad concepto de que usted describir sonidos bastante cerca del concepto de tiempo infinito máquinas de Turing, que amplían el funcionamiento ordinario de máquinas de Turing en el ordinal transfinito tiempo, y por lo tanto proporcionan un sólido modelo matemático de supertask la computación. La idea básica de la ITTM modelo es permitir que un ordinario de la máquina de Turing para operar en el ordinal transfinito tiempo, definiendo el límite de configuración y permitir que continúe su operación. En sucesor de los números ordinales, la máquina funciona de acuerdo a la rígida instrucciones de su finita programa. En un límite de la etapa, la cabeza es restablecer en más a la izquierda de la celda, el nuevo estado es un tipo especial de límite de estado, y cada celda de la cinta es actualizado por la toma de las $\limsup$ de los valores que se muestran en la que la célula va al límite.
La referencia principal es mi papel con Andy Lewis: J. D. Hamkins, A. Lewis, "tiempo Infinito máquinas de Turing", J. de la Lógica Simbólica 65, 2000, pág. 567-604. Las máquinas se han definido por primera vez por Jeff Kidder y yo.
En el ITTM modelo, se investigó tanto la complejidad de los conjuntos que se de un tiempo infinito decidable, así como la longitud de tiempo que tales cálculos tomar. Resulta que no sólo son todos los de la aritmética establece un tiempo infinito decidable---y así, toda la aritmética preguntas de teoría de los números son decidable por tales máquinas---pero la colección de un tiempo infinito decidable conjuntos alcanza trivial en la proyectiva de la jerarquía, más allá de la hyperarithmetic conjuntos de $\Delta^1_1$ y, de hecho, más allá de la lightface analíticos conjuntos de $\Sigma^1_1$ y a las $\Delta^1_2$ conjuntos. Mucho más complicado preguntas pueden ser resueltas por estas máquinas. Por ejemplo, con tiempo infinito máquinas de Turing, uno puede probar una contables de la orden en cuanto a si está bien fundada, que es en general una completa $\Pi^1_1$-prueba. En el ITTM contexto, hay una teoría muy interesante sobre el supremum de las longitudes de la detención de los cálculos en comparación con la longitud de la estabilización de los cálculos en comparación con las longitudes de los que aún no la repetición de los cálculos. Los ordinales donde estos fenómenos se producen son conocidos como $\lambda$, $\zeta$ y $\Sigma$, y están íntimamente conectadas con ciertas fina-características estructurales de la edificable jerarquía. Por ejemplo, Philip Welch demostrado que $L_\lambda\prec_{\Sigma_1}L_\zeta\prec_{\Sigma_2}L_\Sigma$, y de los ordinales se caracteriza por ser el menos el triple de los números ordinales con esa propiedad, un resultado que se ha conocido como el $\lambda$-$\zeta$-$\Sigma$ teorema.
La media aritmética de los conjuntos son exactamente aquellos conjuntos que son decidable uniformemente en el tiempo $\omega^2$, con límite dándole esencialmente dos adicionales aritmética de los cuantificadores. El hyperarithemtic conjuntos son exactamente los conjuntos uniformemente decidable en el tiempo a menos de $\omega_1^{ck}$, el supremum de la computables ordinales. Mientras tanto, el clockable y escribir los números ordinales llegar mucho más alto que esto.
No todos los conjuntos son infinitos tiempo decidable, por supuesto, ya que sólo hay countably muchos programas, y por tanto sólo countably muchos decidable conjuntos. De hecho, hay un tiempo infinito analógica de la detención problema, que es infinito en tiempo semi-decidable pero no a tiempo infinito decidable. También hay un análogo de Turing grados para este contexto, con dos saltar operadores, correspondiente a la negrita y lightface detener los problemas, para lo cual se permite o no permite reales de los parámetros.
Puede consultar esta lista de mis artículos sobre el tema, cuyas bibliografías contienen referencias a las cada vez más grandes de la literatura sobre el tema. Ahora hay un tiempo infinito análogos de la computabilidad teoría, la teoría de la complejidad, la equivalencia de la relación de la teoría y mucho más.
