You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

PhilGoetz comments on Bragging thread August 2015 - Less Wrong Discussion

3 Post author: philh 01 August 2015 07:46PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (43)

You are viewing a single comment's thread. Show more comments above.

Comment author: PhilGoetz 21 August 2015 05:09:24PM *  1 point [-]

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.

Comment author: gjm 21 August 2015 06:40:32PM *  0 points [-]

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.