X-Message-Number: 8596 Date: Mon, 15 Sep 1997 17:07:53 -0400 From: "John P. Pietrzak" <> Subject: More on Turing Machines & etc. References: <> Hi Thomas, Yes, you're absolutely right, there was never any intention of creating a real-world "Turing Machine". The structure of the TM is simply a combination of several abstract concepts. It is of value because (a) it has a clear, concise, and (relatively) simple mathematical definition, and (b) it can be shown that (IGNORING THE LIMITS OF TIME AND SPACE) anything which can be performed by a digital processor can be performed by a Turing Machine. Just the sort of thing you want when you'd like to prove general theories about computation. [On neural nets:] > Recognition is not a task performable by a PRACTICAL Turing machine. Let me repeat, there is _no such thing_ as a PRACTICAL Turing Machine. [On the unique distributed memory system of the brain:] > Question: the classical Turing machine is given a tape, which it > moves along marking individual digital spaces. If we allow formation > of new connections and even new neurons, this tape becomes endless > not only at both ends but even in the middle. Ah, but you see, this is the magic of defining the tape as "infinite"; you can always "add" more space in the middle, by moving everything to the right of it over a few spaces. Of course, the process of moving each mark, one by one, over a few spaces, can be incredibly inefficient and time consuming for a TM; but since it's an imaginary machine anyway, we don't care. All we want to do is show that it is *possible*. > I am certainly aware of all the ideas for mapping, say, a digital > N-dim infinite set of points to a single 1-dim sequence of points. > Perhaps that solves the problem of equivalence and perhaps not: > remember that such a mapping would have to change constantly as the > Turing machine proceeded. Indeed, classically, those ideas for mapping multi-dimensional to single-dimensional spaces are exactly what people use in many TM proofs. (In fact, here in Hopcroft & Ullman's book, pp. 164 - 165, they give an example of just that.) But then, with the brain, we're not even talking about infinite sets of points: we have a large but finite set of neurons (which changes at some rate) with a large but finite set of interconnections between themselves (which changes at some rate). For example, let's say I want to simulate the (changing) inter- connections between neurons, nothing else. First, let me assume that I can give a unique name to each neuron that exists in a person's brain over their lifespan. (If we're going to simulate a person's brain on a computer, we're at least going to have to simulate each individual neuron that exists at a specific time, and if we want the simulation to be accurate, the set of neurons is likely to change over time; I assume such a simulation would have to treat each neuron separately.) Let me simply use integers to name them: neuron 1, neuron 2, etc. Second, let me assume that I can use a single value to simulate the link(s) between any two neurons at a given time (for simplicity). Then, given neurons 1,2,3,...,n at a given time, I can use the following table to record which neurons have connections to which other neurons: neuron name 1 2 3 ... n neuron 1 x x x x name 2 x x x x 3 x x x x . . . . . . n x x x ... x (Where each x is filled in with an appropriate link value.) This 2-d structure can be mapped into a single dimension, as you noted, using various systems. Therefore, it's not too tough to show that such a structure could be encoded into a TM. As the links change, I simply change the link values between the neurons. If we should happen to run out of names for each neuron, it's probably simplest to construct a new, larger table further on down the tape (we've got as much tape space as you want) and copy the data from the old table to the new one. Generally, I suspect that as long as all we're talking about is simulating a finite number of connections between a finite number of neurons, there isn't any problem with showing a TM could do it. Other problems, for example dealing with the signals sent between neurons, might be tougher if they turn out to be interpreted in an analog rather than digital manner; a digital approximation may or may not be sufficient to encode them. John Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8596