A Turing machine has an infinite tape with 1s and 0s that acts as a memory. Where does it get the instruction to perform a task? Are the instruction written on the tape? Because from what I understand, the machine reads what’s written on the tape and then perform some instruction on that same tape. So it replaces the input data with output date?
In: 4
Yes, you have it right. Mostly.
The Turing machine has a set of hard-coded rules inside of itself that tell it how to behave when it reads values on the tape. You get to set those rules ahead of time. They can be as simplistic or complex as you like.
Technically speaking, the term “Turing machine” actually refers to that set of rules, never an actual physical machine. You can build a real-world physical machine that carries out the operations of your Turing machine if you want to, but that physical machine itself is not a “Turing machine”. Just an implementation of one. For sake of simplicity, though, let’s just assume you’ve built a machine like that, and we’ll just call it a “Turing machine” to save time.
Unlike the kind of computer program you may be thinking of, the Turing machine can’t do things like store variables “in its head”. All it can do is read the cell of the tape it’s currently over, and decide right then and there what to do next based on what it’s just read, everything has read up to this point, and the logic of the program it had pre-loaded from the start. If it wants to store memory for later, it will have to do that by writing data onto the tape somewhere.
As you said, the “output” of the computation is whatever the state of the tape is whenever the Turing machine decides it’s time to stop. That *could* mean the machine writing over the data already on the tape, if the Turing machine is programmed to behave that way. But it just as well could be programmed to write that data somewhere else on the tape, leaving the program intact.
Overwriting the instructions on the tape may initially sound like a bad thing, but it isn’t really an issue. If the machine works, it works, right? All you care about is the answer. If it mangles its own input in the process, who cares? If you need to use the machine again you’ll just reset the tape anyway. Programming the machine to dump the answer in a special designated place that doesn’t overwrite the instructions is mostly a convenience feature that makes it so you don’t have to reset as much tape between uses. Which is entirely moot if the Turing machine is just an imaginary one (and, like I said before, when technically speaking, all of them are).
Latest Answers