Norm writes > You [Hal Finney] say, ". . . the Church Thesis, which I would paraphrase > as saying that there are no physical processes more computationally > powerful than a Turing machine, or in other words that the universe could > in principle be simulated on a TM. I wouldn't be surprised if most people > who believe that minds can be simulated on TMs also believe that > everything can be simulated on a TM." > > I'm out of my depth here, but this doesn't make sense to me. My > understanding is that the Turing Machine is a hypothetical device.
Unfortunately, the "Turing Machine" is often taken to be either one of *two* possibilities. One is, as you say, a "device". All the usual paraphernalia of a normal computer is abstracted away, leaving the least possible behavior that could still do computing. Turing, of course, began with the simplest operations that he could conceive of a human "computer" doing. In this first view, we arrive at the usual picture of a little box on wheels which scans a tape one square at a time, and either writes a zero or a 1, and then moves left or right on the tape depending also on what it scanned. But there is a second meaning to "Turing Machine" that is also used extensively in the literature. This has utterly nothing to do with devices. Mathematically, a Turing Machine is a set of quintuples (quadruples in many treatments, e.g. Boolos and Jeffrey). These quintuplets have only mathematical or platonic existence. Yet one can see that by their nature were they implemented in the flesh, so to speak, they could accomplish a specific computation as spelled out by the entries in the five slots of each quintuplet. (Four slots, slightly simpler, are composed of two that specify the current state you're in and the current symbol you're reading, and two composed of the output: the symbol you write and the next state you go to.) Sometimes discussions ensue when one party is talking about an actual (though theoretical) device, and the other is talking about the mathematical description. So beware the term "Turing Machine", unless it's clear which interpretation is meant. > If one could be built that operated at faster-than-light or infinite > speed, maybe it could, in principle, simulate the universe. However, > this isn't possible. Does this mean that the Church Thesis, hence > computationalism, is, in reality, false? No, this doesn't affect Church's Thesis, as probably some here will explain better than I. Sometimes one does encounter "Zeno machines" in the literature, which can solve a harder class of problems because it's assumed that they can complete an infinite number of steps in finite time. But Church's Thesis merely says that every effective computation (that anyone has been able to think of) can be calculated by a Turing machine. It turns out that this specification of Turing machine is completely equivalent to several other reasonable ways calculations can in principle be done, e.g., Post-production strings, recursive functions, "abacus computable functions", and so on. The "thesis" part is that this whole class of equivalent capability is *all* that a computation can be. "Computationalism" is yet another claim. It's the notion that all of our own thoughts as well could be implemented on a Turing Machine in a way that would deliver to us just as much experiential satisfaction. Lee