Return to Answer

There is a body of literature on the topic of supertasks, which are computational tasks involving infinitely many steps. A large part of this work involves a purely mathematical analysis and development of the concept, such as my work on infinite time Turing machines ("Infinite time Turing machines," with Andy Lewis in the Journal of Symbolic Logic, 65(2):567-604, 2000, ArXiv version) and other work on higher recursion theory, E-recursion and other infinitary models of computability. All of these computational models exhibit functions that are not computable by Turing machines, but are computable with respect to the infinitary model. (See this MO answer for an entertaining supertask example.)

Another part of the work,however, has considered the topic of your question, about the extent to which we might actually hope to carry out such infinitary computations. The idea is that the real universe exhibits relativistic phenomenon of which we might take advantage for computational effect, and doing so might take us beyond the Turing barrier. Hogarth and others have described physical models, Malament-Hogarth spacetimes, in which one observer has access to the results of an infinite computation carried out by another in that world. To get the idea, imagine assigning your graduate students, and their graduate students and so on in perpetuity, the task of searching for an arithmetic counterexample, while flying in ever-faster rockets around the Earth, signaling when a counterexample has been found. Because of relativistic time foreshortening, their entire infinite journey will amount to a total finite amount of time for you, and so you can get the answer in finite time.

Philip Welch recently wrote an excellent survey and also this article describing some of the physical models in which one can compute non-computable functions by a physical procedure, among several other articles on the topic on his web page.

There is a body of literature on the topic of supertasks, which are computational tasks involving infinitely many steps. A large part of this work involves a purely mathematical analysis and development of the concept, such as my work on infinite time Turing machines ("Infinite time Turing machines," with Andy Lewis in the Journal of Symbolic Logic, 65(2):567-604, 2000, doi:10.2307/2586556, arXiv version) and other work on higher recursion theory, E-recursion and other infinitary models of computability. All of these computational models exhibit functions that are not computable by Turing machines, but are computable with respect to the infinitary model. (See this MO answer for an entertaining supertask example.)

Another part of the work,however, has considered the topic of your question, about the extent to which we might actually hope to carry out such infinitary computations. The idea is that the real universe exhibits relativistic phenomenon of which we might take advantage for computational effect, and doing so might take us beyond the Turing barrier. Hogarth and others have described physical models, Malament-Hogarth spacetimes, in which one observer has access to the results of an infinite computation carried out by another in that world. To get the idea, imagine assigning your graduate students, and their graduate students and so on in perpetuity, the task of searching for an arithmetic counterexample, while flying in ever-faster rockets around the Earth, signaling when a counterexample has been found. Because of relativistic time foreshortening, their entire infinite journey will amount to a total finite amount of time for you, and so you can get the answer in finite time.

Philip Welch recently wrote an excellent survey and also this article describing some of the physical models in which one can compute non-computable functions by a physical procedure, among several other articles on the topic on his web page.

There is a body of literature on the topic of supertasks, which are computational tasks involving infinitely many steps. A large part of this work involves a purely mathematical analysis and development of the concept, such as my work on infinite time Turing machines ("Infinite time Turing machines," with Andy Lewis in the Journal of Symbolic Logic, 65(2):567-604, 2000, ArXiv version) and other work on higher recursion theory, E-recursion and other infinitary models of computability. All of these computational models exhibit functions that are not computable by Turing machines, but are computable with respect to the infinitary model. (See this MO answer for an entertaining supertask example.)

Another part of the work,however, has considered the topic of your question, about the extent to which we might actually hope to carry out such infinitary computations. The idea is that the real universe exhibits relativistic phenomenon of which we might take advantage for computational effect, and doing so might take us beyond the Turing barrier. Hogarth and others have described physical models, Malament-Hogarth spacetimes, in which one observer has access to the results of an infinite computation carried out by another in that world. To get the idea, imagine assigning your graduate students, and their graduate students and so on in perpetuity, the task of searching for an arithmetic counterexample, while flying in ever-faster rockets around the Earth, signaling when a counterexample has been found. Because of relativistic time foreshortening, their entire infinite journey will amount to a total finite amount of time for you, and so you can get the answer in finite time.

Philip Welch recently wrote an excellent survey and also this article describing some of the physical models in which one can compute non-computable functions by a physical procedure, among several other articles on the topic on his web page.

There is a body of literature on the topic of supertasks, which are computational tasks involving infinitely many steps. A large part of this work involves a purely mathematical analysis and development of the concept, such as my work on infinite time Turing machines ("Infinite time Turing machines," with Andy Lewis in the Journal of Symbolic Logic, 65(2):567-604, 2000, ArXiv version) and other work on higher recursion theory, E-recursion and other infinitary models of computability. All of these computational models exhibit functions that are not computable by Turing machines, but are computable with respect to the infinitary model. (See this MO answer for an entertaining supertask example.)

Another part of the work,however, has considered the topic of your question, about the extent to which we might actually hope to carry out such infinitary computations. The idea is that the real universe exhibits relativistic phenomenon of which we might take advantage for computational effect, and doing so might take us beyond the Turing barrier. Hogarth and others have described physical models, Malament-Hogarth spacetimes, in which one observer has access to the results of an infinite computation carried out by another in that world. To get the idea, imagine assigning your graduate students, and their graduate students and so on in perpetuity, the task of searching for an arithmetic counterexample, while flying in ever-faster rockets around the Earth, signaling when a counterexample has been found. Because of relativistic time foreshortening, their entire infinite journey will amount to a total finite amount of time for you, and so you can get the answer in finite time.

Philip Welch recently wrote an excellent survey and also this article describing some of the physical models in which one can compute non-computable functions by a physical procedure, among several other articles on the topic on his web page.

There is a body of literature on the topic of supertasks, which are computational tasks involving infinitely many steps. A large part of this work involves a purely mathematical analysis and development of the concept, such as my work on infinite time Turing machines ("Infinite time Turing machines," with Andy Lewis in the Journal of Symbolic Logic, 65(2):567-604, 2000, ArXiv version) and other work on higher recursion theory, E-recursion and other infinitary models of computability. All of these computational models exhibit functions that are not computable by Turing machines, but are computable with respect to the infinitary model. (See this MO answer for an entertaining supertask example.)

Another part of the work,however, has considered the question of the extent to which we might actually hope to carry out such infinitary computations. The idea is that the real universe exhibits relativistic phenomenon of which we might take advantage for computational effect. Doing so might take us beyond the Turing barrier. Hogarth and others have described physical models (Malament-Hogarth spacetimes) in which one observer has access to the results of an infinite computation carried out by another in that world. (To get the idea, imagine taking advantage of extreme relativistic time foreshortening.)

(But please beware! Although the area includes some very interesting high-quality work, it has also attracted some rather more questionable research, which I do not recommend.)

Meanwhile, allow me to strongly endorse the work of Philip Welch, who recently wrote an excellent survey describing some of the physical models in which one can compute non-computable functions by a physical procedure, among several other articles on the topic on his web page.

There is a body of literature on the topic of supertasks, which are computational tasks involving infinitely many steps. A large part of this work involves a purely mathematical analysis and development of the concept, such as my work on infinite time Turing machines ("Infinite time Turing machines," with Andy Lewis in the Journal of Symbolic Logic, 65(2):567-604, 2000, ArXiv version) and other work on higher recursion theory, E-recursion and other infinitary models of computability. All of these computational models exhibit functions that are not computable by Turing machines, but are computable with respect to the infinitary model. (See this MO answer for an entertaining supertask example.)

Another part of the work,however, has considered the topic of your question, about the extent to which we might actually hope to carry out such infinitary computations. The idea is that the real universe exhibits relativistic phenomenon of which we might take advantage for computational effect, and doing so might take us beyond the Turing barrier. Hogarth and others have described physical models, Malament-Hogarth spacetimes, in which one observer has access to the results of an infinite computation carried out by another in that world. To get the idea, imagine assigning your graduate students, and their graduate students and so on in perpetuity, the task of searching for an arithmetic counterexample, while flying in ever-faster rockets around the Earth, signaling when a counterexample has been found. Because of relativistic time foreshortening, their entire infinite journey will amount to a total finite amount of time for you, and so you can get the answer in finite time.

Philip Welch recently wrote an excellent survey and also this article describing some of the physical models in which one can compute non-computable functions by a physical procedure, among several other articles on the topic on his web page.