<p>I think we have a reference here to <a href="http://arxiv.org/pdf/math/9808093.pdf" rel="nofollow">Joel Hamkin's model of infinite time computation</a>, 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.</p>

CC BY-SA 3.0
2014-07-18T13:17:34.873Z
couldn't there be that this becomes a problem, if some physical particularity (like black holes) allows for infinite time computation, but we cannot take advantage of it because of the space issue?
Denis
CC BY-SA 3.0
2014-07-18T13:37:59.920Z
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
CC BY-SA 3.0
2014-07-19T00:30:13.537Z
Why wouldn't the same argument "show" that logarithmic space is a strict subset of polynomial time: in polynomial time, polynomially many cells could be written, and they might all be necessary. What this argument seems to be missing is that we are allowed to entirely change the algorithm in order to save space. Just to be clear, I agree that, by Peter's argument, in any reasonable model finite space should be contained in finite time.
Sasho Nikolov
CC BY-SA 3.0
2014-07-19T12:54:22.143Z
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
CC BY-SA 3.0
2014-07-18T06:24:32.950Z
2014-07-18T06:24:32.950Z
Andrej Bauer
<p>Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?</p>

CC BY-SA 3.0
2014-07-16T16:14:55.220Z
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 
CC BY-SA 3.0
2014-07-16T19:59:19.710Z
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
CC BY-SA 3.0
2014-07-17T03:08:47.097Z
I would say infinite-time Turing machine. I was not originally limiting to infinite-time Turing machine, though.
Inducto
CC BY-SA 3.0
2014-07-17T06:23:00.623Z
Then @Peter's comment answers your question. I this is more suitable for [cs.se], it is an undergraduate exercise to show that $space \leq time \leq 2^{O(space)}$.
Kaveh
<computability><turing-machines><space-complexity><hypercomputation>
Does hyper-computational power of infinite time Turing machines also require infinite memory?
Inducto
# Does hyper-computational power of infinite time Turing machines also require infinite memory?

(Asked by: username_0 on 2014-07-16)

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

**Tags:** computability, turing-machines, space-complexity, hypercomputation
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  
> **username_0**: I would say infinite-time Turing machine. I was not originally limiting to infinite-time Turing machine, though.  
> **username_2**: Then @Peter's comment answers your question. I this is more suitable for [cs.se], it is an undergraduate exercise to show that $space \leq time \leq 2^{O(space)}$.  

---

## 1 answers

### Answer by username_3 on 2014-07-18. Score: 4

I think we have a reference here to [Joel Hamkin's model of infinite time computation](http://arxiv.org/pdf/math/9808093.pdf), 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.

> **Comments:**
> **username_4**: couldn't there be that this becomes a problem, if some physical particularity (like black holes) allows for infinite time computation, but we cannot take advantage of it because of the space issue?  
> **username_3**: 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.  
> **username_5**: Why wouldn't the same argument "show" that logarithmic space is a strict subset of polynomial time: in polynomial time, polynomially many cells could be written, and they might all be necessary. What this argument seems to be missing is that we are allowed to entirely change the algorithm in order to save space. Just to be clear, I agree that, by Peter's argument, in any reasonable model finite space should be contained in finite time.  
> **username_3**: 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.  

---

