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
A Turing machine is a logical construct, not an actual functioning machine. It’s basically just a list of requirements: the bare minimum some machine must be able to do in order to say that it can solve any arbitrary problem (as opposed to being a machine purpose-built to solve a small subset of possible problems).
A Turing machine is a logical construct, not an actual functioning machine. It’s basically just a list of requirements: the bare minimum some machine must be able to do in order to say that it can solve any arbitrary problem (as opposed to being a machine purpose-built to solve a small subset of possible problems).
A Turing machine is a logical construct, not an actual functioning machine. It’s basically just a list of requirements: the bare minimum some machine must be able to do in order to say that it can solve any arbitrary problem (as opposed to being a machine purpose-built to solve a small subset of possible problems).
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).
It’s not necessarily 1s and 0s. It can be any symbol of a specified alphabet.
It has an infinite 1D tape and keeps track of a state and location on the tape. It repeatedly reads from the tape at the current position, writes to the tape at the current position, changes state, and moves around the tape. The new state, symbol written, and direction of movement (magnitude is always 1) depend on the old state and symbol read. The interpretation of said symbols is completely external; the Turing machine has no idea what they mean.
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).
A CPU is a modern example, but not definition of a Turing machine. Inside is a register (place to store information, like a variable in Algebra) called the program counter which points to a cell in memory. For most programs, memory is essentially an endless tape where each cell can store a binary number from 0 to 2^(n)-1 for however many bits the CPU is designed for. In reality, there is a limit to how many cells there are, but you shouldn’t typically have to worry about it.
The instructions come from the RAM and a decoder. Basically, the CPU is filled with machines to do jobs. The ALU is the most important one as it can add, subtract, AND, OR, NOT, and any other number of functions. There’s a flags register which is our main way of checking the result of an operation, which allows us to branch given certain scenarios (typically a zero, negative, and overflow/carry flag are used). The instructions can read from the flags and run certain operations given the results. The operations are typically run through a decoder. For instance ADD in assembly will have several steps, to pull the instruction from memory to the instruction register, increment the program counter, move to the correct address in RAM, put that value in the ALU, add to the appropriate register and update flags. The decoder will act like the gears and knobs of a machine to make all the little pieces work. The program in RAM will act like the operator of the machine.
But remember, that’s just one example of a Turing Machine, not the definition. But that’s one way in which we can make it work. Basically, the RAM values, program counter, and flags and data registers act as our states. The program counter has a jump/increment feature which acts as our way to move backwards and forwards on the tape. RAM is the tape, and the decoder (along with the instructions written into RAM) acts like our decision tree
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).
It’s not necessarily 1s and 0s. It can be any symbol of a specified alphabet.
It has an infinite 1D tape and keeps track of a state and location on the tape. It repeatedly reads from the tape at the current position, writes to the tape at the current position, changes state, and moves around the tape. The new state, symbol written, and direction of movement (magnitude is always 1) depend on the old state and symbol read. The interpretation of said symbols is completely external; the Turing machine has no idea what they mean.
The thing about this idealized Turing machine is that it is just a thought experiment. Turing was able to mathematically show that this machine was the minimum required to do any calculation that any deterministic machine could do (and more to the point, that they could all do this), the only limiting factor is time and space.
It is like saying that you can make any building with tweezers and a tiny blowtorch, given enough time and a big enough pile of sand.
Latest Answers