Well-founded Iterations of Infinite Time Turing Machines

2015/10/02 by Robert S. Lubarsky, Lubarsky, Robert
Computer Science · #03D60 #03E10 #03E75 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Quantum Computing Algorithms and Architecture

paper · pdf · doi:10.48550/arxiv.1510.00691

openalex publication_date 2015/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Infinite time Turing machines are extended in several ways to allow for iterated oracle calls. The expressive power of these machines is discussed and in some cases determined.

Related

• Toward higher-order infinite time Turing machines: simulational Γ-machines
• Infinite Time Turing Machines: Supertask Computation
• Supertask Computation
• Lower bounds on β(α) and other properties of α-ITRMs
• Infinite time Turing machines with only one tape