1
$\begingroup$

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

$\endgroup$
  • 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 Shor Jul 16 '14 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$ – Kaveh Jul 16 '14 at 19:59
  • $\begingroup$ I would say infinite-time Turing machine. I was not originally limiting to infinite-time Turing machine, though. $\endgroup$ – Inducto Jul 17 '14 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$ – Kaveh Jul 17 '14 at 6:23
3
$\begingroup$

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.

$\endgroup$
  • $\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$ – Denis Jul 18 '14 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$ – Andrej Bauer Jul 18 '14 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$ – Sasho Nikolov Jul 19 '14 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$ – Andrej Bauer Jul 19 '14 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.