Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?
$\begingroup$
$\endgroup$
4
-
5$\begingroup$ 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. $\endgroup$– Peter ShorCommented Jul 16, 2014 at 16:14
-
3$\begingroup$ 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? $\endgroup$– KavehCommented Jul 16, 2014 at 19:59
-
$\begingroup$ I would say infinite-time Turing machine. I was not originally limiting to infinite-time Turing machine, though. $\endgroup$– InductoCommented Jul 17, 2014 at 3:08
-
2$\begingroup$ 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)}$. $\endgroup$– KavehCommented Jul 17, 2014 at 6:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Jul 18, 2014 at 6:24
-
$\begingroup$ 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? $\endgroup$– DenisCommented Jul 18, 2014 at 13:17
-
1$\begingroup$ 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. $\endgroup$ Commented Jul 18, 2014 at 13:37
-
$\begingroup$ 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. $\endgroup$ Commented Jul 19, 2014 at 0:30
-
$\begingroup$ 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. $\endgroup$ Commented Jul 19, 2014 at 12:54