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
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.
Latest Answers