Infinite Time Computation: Strong and Weak Infinite Time Turing Machines

Hamkins and Lewis have used infinite time Turing machines to extend the operations of Turing machines to infinite ordinal time. This project investigates some applications of these machines to basic operations and relations over the reals. It also investigates variants of these machines with extra-tapes or extra read-write heads. Then, this project investigates strictly weaker variants of these machines, which are obtained by allowing the content in each cell to change only finitely often. It is shown that these weaker machines can already compute basic operations and relations over the reals. Finally, the computational power of these machines is further investigated.