If such a machine existed in our universe, as it sped up its execution, its parts would approach the speed of light. To continue speeding up its execution, it necessarily must occupy a smaller and smaller volume, to keep the parts nearer and nearer to each other. Continue further, and you realize that the total information content of the machine can't be sustained at any amount without the thing collapsing itself into a black hole. So, even if the machine, in any sense, "finishes" the computation, the output will live inside a black hole and thus be physically unknowable to us.<p>I find it so fascinating that fundamental properties about the laws of physics integrate so tightly with what is computable. The standard definition of compatibility involving Turing machines sounds kind of arbitrary, but those machines are representative a truly fundamental concept in our universe: that which is physically knowable, since you can build Turing machines out of the stuff in the universe.<p>Almost. Turing machines have unbounded tape. But the universe does not contain an unbounded amount of information or space with which to work. Sufficiently large Turing computations, though theoretically finite, are not realizable in our universe. Should such computations be considered decidable or undecidable?