Timeline for Does hyper-computational power of infinite time Turing machines also require infinite memory?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 19, 2014 at 12:54 | comment | added | Andrej Bauer | 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. | |
| Jul 19, 2014 at 0:30 | comment | added | Sasho Nikolov | 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. | |
| Jul 18, 2014 at 13:37 | comment | added | Andrej Bauer | 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. | |
| Jul 18, 2014 at 13:17 | comment | added | Denis | 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? | |
| Jul 18, 2014 at 6:24 | history | answered | Andrej Bauer | CC BY-SA 3.0 |