recursion theory. Theory of Recursive Functions and Effective Computability by Hartley Rogers. A theory about what’s computable is part of recursion theory, but it turns out that there’s a lot more that’s known about the realm of the uncomputable than one might expect.
hypercomputation. Various papers by Toby Ord. This is related to the above, but more about how one might practically realize the higher forms of computation. I just noticed there’s a recent book about this topic. Hypercomputation: Computing Beyond the Church-Turing Barrier by Apostolos Syropoulos.
Hypercomputation seems like a misguided attack on the Church-Turing thesis to me. If nobody can build a hypercomputer—and there’s no evidence that anyone ever will be able to—then I am not sure I can see what the point is.
I guess it’s because there is no proof that someone won’t find a way of computing the uncomputable. It seems unlikely to me—but I suppose there is not much harm in philosopers speculating.
Re: Toby’s “Regardless of the actual computational limits of our universe, I have no doubt that the study of hypercomputation will lead to many important theoretical results across computer science, philosophy, mathematics and physics.”
Hmm. What have we got so far out of Omegas and Oracles? I expect what we will get out of Hypercomputation will be mostly confusion—since it sounds as though it is a field with a real object of study.
Well, one practical result we’ve got is that we shouldn’t program AIs to assume (either implicitly or explicitly) that the universe must be computable. See this discussion between Eliezer and me about this.
To start things off, here are my entries:
recursion theory. Theory of Recursive Functions and Effective Computability by Hartley Rogers. A theory about what’s computable is part of recursion theory, but it turns out that there’s a lot more that’s known about the realm of the uncomputable than one might expect.
hypercomputation. Various papers by Toby Ord. This is related to the above, but more about how one might practically realize the higher forms of computation. I just noticed there’s a recent book about this topic. Hypercomputation: Computing Beyond the Church-Turing Barrier by Apostolos Syropoulos.
Hypercomputation seems like a misguided attack on the Church-Turing thesis to me. If nobody can build a hypercomputer—and there’s no evidence that anyone ever will be able to—then I am not sure I can see what the point is.
I guess it’s because there is no proof that someone won’t find a way of computing the uncomputable. It seems unlikely to me—but I suppose there is not much harm in philosopers speculating.
Re: Toby’s “Regardless of the actual computational limits of our universe, I have no doubt that the study of hypercomputation will lead to many important theoretical results across computer science, philosophy, mathematics and physics.”
Hmm. What have we got so far out of Omegas and Oracles? I expect what we will get out of Hypercomputation will be mostly confusion—since it sounds as though it is a field with a real object of study.
Well, one practical result we’ve got is that we shouldn’t program AIs to assume (either implicitly or explicitly) that the universe must be computable. See this discussion between Eliezer and me about this.
Making agents with assumptions about anything which we are not confident of the truth of seems like a dubious strategy.
We are fairly confident of the Church-Turing thesis, though: “Today the thesis has near-universal acceptance” - http://en.wikipedia.org/wiki/Church–Turing_thesis