Could some other people who have read Causal Universes comment on whether EY implies in it that hypercomputation is possible? What is hypercomputation?
EY doesn’t imply that hypercomputation is possible in our universe. He does imply that there are logically possible universes in which hypercomputation is possible. Hypercomputation is any computational process that is able to evaluate at least one non-Turing-computable function.
(That last definition may be unhelpful in practice. If our universe is finite then it can’t contain anything that’s even Turing-powerful, never mind capable of hypercomputation. If our own lifespan and perceptual powers are finite then there’s no way we could ever know anything was doing hypercomputation.)
Hypercomputation is any computational process that is able to evaluate at least one non-Turing-computable function.
What about computing a Turing-computable function in O(m) time, where a Turing machine needs O(n) and m < n? Does quantum computation count as hypercomputation? The Wikipedia page seems to say no.
I’d agree with Wikipedia. After all, there are plenty of other physically-realizable models of computation that are equivalent to Turing machines in terms of what they can compute but substantially inequivalent in terms of how long it takes.
[EDITED to add:] … Though I think anything you can do in a Newtonian universe can be modelled on a Turing machine with at worst a polynomial-in-problem-size slowdown. So there might be something to be said for counting as “hypercomputation” anything that, e.g., can evaluate all computable functions in constant time. But that isn’t the usual use of the term.
Could some other people who have read Causal Universes comment on whether EY implies in it that hypercomputation is possible? What is hypercomputation?
EY doesn’t imply that hypercomputation is possible in our universe. He does imply that there are logically possible universes in which hypercomputation is possible. Hypercomputation is any computational process that is able to evaluate at least one non-Turing-computable function.
(That last definition may be unhelpful in practice. If our universe is finite then it can’t contain anything that’s even Turing-powerful, never mind capable of hypercomputation. If our own lifespan and perceptual powers are finite then there’s no way we could ever know anything was doing hypercomputation.)
What about computing a Turing-computable function in O(m) time, where a Turing machine needs O(n) and m < n? Does quantum computation count as hypercomputation? The Wikipedia page seems to say no.
I’d agree with Wikipedia. After all, there are plenty of other physically-realizable models of computation that are equivalent to Turing machines in terms of what they can compute but substantially inequivalent in terms of how long it takes.
[EDITED to add:] … Though I think anything you can do in a Newtonian universe can be modelled on a Turing machine with at worst a polynomial-in-problem-size slowdown. So there might be something to be said for counting as “hypercomputation” anything that, e.g., can evaluate all computable functions in constant time. But that isn’t the usual use of the term.