Corey Maley raised some doubts on Brain Hammer, and I offered my reasons for a (qualified) positive answer. If anyone has any thoughts on this, I’d be interested in hearing them.
Do Universal Turing Machines Execute Programs?
4 Comments
Comments are closed.
Gualtiero,
As I think about this more, it occurs to me that there seems to be an analog in the difference between Turing Machines and stored-program computers and the difference between processes that can be said to act in accordance with rules and rule-governed processes. The behavior of a TM (including a UTM) is governed by the configuration of the states of the machine and transitions among the states, whereas the behavior of a stored-program computers is governed by a program. TMs can certainly be said to behave in accordance with certain rules, although I don’t think they are governed by them: the state-transition table of a TM is not actually a set of rules. In this way, they are similar to neural networks.
You are right in saying that “the question of what does and does not count as program execution is, to some extent, a matter of stipulation”. I do think that this is an important aspect of computational theory that needs to be taken seriously, particularly with respect to computational theories in cognitive science. Although the functions that can be computed by both UTMs and sufficiently powerful stored-program computers are identical, understanding and explaining the ways that they function are quite different. For instance, whether the mind/brain implements a particular cognitive function in a state-configuration governed way as opposed to a stored-program governed way is (I would think) an interesting question, each requiring different types of cognitive/neural architectures.
There is much more to be said here, and I certainly haven’t thought it out in any detail. Maybe other Brains readers have thoughts about this?
Suppose that a UTM simulates a program P on data D iff the UTM proceeds through a sequence of instantaneous descriptions (IDs) that is isomorphic (homomorphic?) to the sequence of IDs P goes through in computing D. (Let this be a definition of “simulation” of a P by at UTM.)
Now take UTM and modify it so that for just one particular program P1, it does not compute the value of P1 on D using the algorithm that P1 uses. Call this new program UTM*. (UTM* might begin with the equivalent of a conditional statement, if the program is P1 …) In this case, UTM* would not simulate P1 on D in the technical sense just specified. So, given that definition, it would seem to me to be incorrect to say simply that UTMs simulate programs on data. Some UTMs do, some don’t.
That’s a little short, but I hope the idea is clear enough. I’ve been meaning to read that paper, Gualtiero, but since it’s going to be presented at SSPP, I’ve been waiting to nearer that time when I can talk about it with you.
Thanks, Ken. I look forward to talking with you at the SSPP.
I agree that TMs are governed by state transition tables and that computers are governed by programs, but I disagree that these two kinds of control are mutually exclusive. UTMs are goverened by the conjunction of their state transition table and program (instructions, symbols, whatever you want to call them) written on their tape. Similarly, digital computers are goverened by programs in combination with the state transition table (or finite state automaton, or whatever you want to call it) that describes the behavior of their control and datapath components.
As to being rule-governed vs. acting in accordance with a rule, I think it is, again, partly a matter of stipulation. I am happy to say that all computation is rule-governed, and have said so in print. But I’m all in favor of drawing fine grained distinctions between kinds of computation.