# Does hyper-computational power of infinite time Turing machines also require infinite memory?

Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?

• Since space $S$ machines need never use more than exponential time (that's how many states they have), in order to do infinite-time computation you need infinite-space as well. – Peter Shor Jul 16 '14 at 16:14
• The question is not clear. Space and time may not be defined or even make sense in some models. Which hypercomputation model are you talking about? – Kaveh Jul 16 '14 at 19:59
• I would say infinite-time Turing machine. I was not originally limiting to infinite-time Turing machine, though. – Inducto Jul 17 '14 at 3:08
• Then @Peter's comment answers your question. I this is more suitable for Computer Science, it is an undergraduate exercise to show that $space \leq time \leq 2^{O(space)}$. – Kaveh Jul 17 '14 at 6:23

I think we have a reference here to Joel Hamkin's model of infinite time computation, not just some made up idea of infinite time machines. In that model time is measured by ordinal numbers. The machine has access to an infinite tape. After $\omega$ steps, every cell of the tape has been potentially written to, and we can't throw away any cell because its content may be needed during further computation. So yes, you'd need infinite space, but that's not a problem when you've got infinite time already.
• Only if you can get black holes to let you compute beyond $\omega$ steps. I am aware of theories that show how you get infinite time, but infinitely many infinite times? That would require some serious black hole engineering. – Andrej Bauer Jul 18 '14 at 13:37
• It's an order-theoretic problem, not one of cardinality. Both $\omega$ and $\omega + \omega$ have the same size, namely $\aleph_0$, but one has a limit point in the middle. Presumably you can't get rid of it with physics. To compute for $\omega + \omega$ steps you'd have to somehow fly into a black hole, emerge from it, and then fly into it again. Or something like that. – Andrej Bauer Jul 19 '14 at 12:54