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 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
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.
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.
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.
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
1. It’s not just 1’s and 0’s. A Turing Machine can have an arbitrary number of “symbols”, not just the two. You can have 2 symbols or 1000 symbols, they are all functionally equivalent.
2. A Turing Machine is a mathematical construct. For the purposes of mathematics, it’s a set of rules that you follow. It doesn’t get the “instructions” from anywhere, it’s defined by the person designing the Turing Machine.
3. A Turing Machine can read what is written where the “read head” is positioned. Based on what is read, the “read head” can move to different positions of the tape, read values, or write values. It doesn’t have to replace the input data with the output data, it just has the option to. It can read, move, then write on a blank spot.
A Turing machine’s components can be mapped to a physical computer like this:
1. The tape is the RAM (or HDD/SSD) of the physical computer. The CPU registers are also part of this tape as well.
2. The “read head” is harder to pin down because aspects of it show up in different areas and it’s much deeper in the CPU. In general CPU instructions include memory addresses to read/write data from. That’s part of the read head. If the CPU is a stack machine, the read head also includes the pointer for the current instruction being executed.
3. The instructions are built into the CPU’s transistors. They are the ISA (x86, ARM). This is harder to comprehend because a single instruction in an ISA like x86 can be more like several instructions in a Turing Machine you design. A lot of x86 instructions for example involve reading data from at least 2 memory addresses and writing data to another memory address.
1. It’s not just 1’s and 0’s. A Turing Machine can have an arbitrary number of “symbols”, not just the two. You can have 2 symbols or 1000 symbols, they are all functionally equivalent.
2. A Turing Machine is a mathematical construct. For the purposes of mathematics, it’s a set of rules that you follow. It doesn’t get the “instructions” from anywhere, it’s defined by the person designing the Turing Machine.
3. A Turing Machine can read what is written where the “read head” is positioned. Based on what is read, the “read head” can move to different positions of the tape, read values, or write values. It doesn’t have to replace the input data with the output data, it just has the option to. It can read, move, then write on a blank spot.
A Turing machine’s components can be mapped to a physical computer like this:
1. The tape is the RAM (or HDD/SSD) of the physical computer. The CPU registers are also part of this tape as well.
2. The “read head” is harder to pin down because aspects of it show up in different areas and it’s much deeper in the CPU. In general CPU instructions include memory addresses to read/write data from. That’s part of the read head. If the CPU is a stack machine, the read head also includes the pointer for the current instruction being executed.
3. The instructions are built into the CPU’s transistors. They are the ISA (x86, ARM). This is harder to comprehend because a single instruction in an ISA like x86 can be more like several instructions in a Turing Machine you design. A lot of x86 instructions for example involve reading data from at least 2 memory addresses and writing data to another memory address.
1. It’s not just 1’s and 0’s. A Turing Machine can have an arbitrary number of “symbols”, not just the two. You can have 2 symbols or 1000 symbols, they are all functionally equivalent.
2. A Turing Machine is a mathematical construct. For the purposes of mathematics, it’s a set of rules that you follow. It doesn’t get the “instructions” from anywhere, it’s defined by the person designing the Turing Machine.
3. A Turing Machine can read what is written where the “read head” is positioned. Based on what is read, the “read head” can move to different positions of the tape, read values, or write values. It doesn’t have to replace the input data with the output data, it just has the option to. It can read, move, then write on a blank spot.
A Turing machine’s components can be mapped to a physical computer like this:
1. The tape is the RAM (or HDD/SSD) of the physical computer. The CPU registers are also part of this tape as well.
2. The “read head” is harder to pin down because aspects of it show up in different areas and it’s much deeper in the CPU. In general CPU instructions include memory addresses to read/write data from. That’s part of the read head. If the CPU is a stack machine, the read head also includes the pointer for the current instruction being executed.
3. The instructions are built into the CPU’s transistors. They are the ISA (x86, ARM). This is harder to comprehend because a single instruction in an ISA like x86 can be more like several instructions in a Turing Machine you design. A lot of x86 instructions for example involve reading data from at least 2 memory addresses and writing data to another memory address.
In his 1936 paper Turing includes various tables that define (in the left column) a *Configuration* and (in the right column) a *Behaviour*.
It is by following these tables that a Turing machine gets its “instructions” on exactly how to process a “tape”.
At a very simple level these tables can be considered the Turing Machine programming language.
If you want some examples I would recommend “The Annotated Turing” book written by Charles Petzold, which takes you through the process of how this works in small steps.
In his 1936 paper Turing includes various tables that define (in the left column) a *Configuration* and (in the right column) a *Behaviour*.
It is by following these tables that a Turing machine gets its “instructions” on exactly how to process a “tape”.
At a very simple level these tables can be considered the Turing Machine programming language.
If you want some examples I would recommend “The Annotated Turing” book written by Charles Petzold, which takes you through the process of how this works in small steps.
Latest Answers