Timeline for Does the Axiom of Choice (or any other "optional" set theory axiom) have real-world consequences?
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2010 at 2:22 | comment | added | Ryan O'Donnell | Here is a completely serious paper about computation and closed timelike curves, by two top quantum computer scientists: arxiv.org/PS_cache/arxiv/pdf/0808/0808.2669v1.pdf The gist of it is that if closed timelike curves exist, then quantum computers are no more powerful than classical computers (although both become superpowerful, they become equally superpowerful). | |
| Jun 9, 2010 at 2:16 | comment | added | Timothy Chow | You can find many such proposals by googling for "hypercomputation." But even if we take such proposals seriously, there is a problem. Say we construct a physical theory that tells us how to build a hypercomputer to solve the halting problem. We build the hypercomputer and ask it, "Would a Turing machine programmed to find a contradiction in ZFC halt?" Say the hypercomputer replies, "No." Have we "proved" that ZFC is consistent? I don't think so. We can't rule out the possibility that ZFC is inconsistent but that there is something wrong with our physical theory about the hypercomputer. | |
| Jun 8, 2010 at 12:54 | comment | added | Joel David Hamkins | Philip Welch has an excellent mathematical summary of these ideas at maths.bris.ac.uk/~mapdw/chapter-fin.pdf (and several other papers on his web page). The idea of building these strange spacetimes to physically realize infinitary computation stretches back at least to Hogarth 1992, with a lot of work since then, and there is currently resurgent active work on the purely mathematical aspects of infinitary computability, such as that arising in Blum-Shub-Smale machines and infinite time Turing machines, with which I have been involved. | |
| Jun 8, 2010 at 7:42 | comment | added | jeremy | Some of my quantum computation friends have mentioned these things, and they all rely on closed timelike curves so that any computation that can be done in finite time can be done in bounded time--including zero time or a negative amount of time! If you're clever, you can get around some of the infinite memory problems by having the computer communicate with past states of itself in a clever manner, IIRC. Then, after explaining this, they laugh and tell me how they're paid to study this... | |
| Jun 8, 2010 at 7:32 | history | answered | gowers | CC BY-SA 2.5 |