There are many references to it in public discussions, but trying to learn about it from Wikipedia is like reading in a new foreign language.
In: 283
You’ve gotten some good answers, but I’ll give it a shot too. A Turing machine is almost like a flowchart, but it has one important addition, memory. Imagine you have a flow chart with some directions and an infinite paper tape divided into cells. One of the cells is designated as the current cell. As you follow the directions in the flowchart, the flowchart might direct you to write a symbol in the cell (erasing whatever used to be there if anything) or to move the current cell left or right by one space. The path you take through the flowchart can depend on the symbol in the current cell. What is computed obviously depends on the flowchart you are following, but Turing proved that it is possible to come up with a flowchart that will emulate the behavior or other flowcharts given the right initial information on the tape. For example, say I come up with a flowchart that will print out the digits of pi. Then I come up with a flowchart that prints out all the squares of the positive integers. These two flow charts have different behaviors. But if you are clever you can come up with a flowchart that reads a description of another flowchart off the tape and then emulates the behavior of the described flowchart.
The practical implication is this. You can design a machine to do one particular computational task. But you can also design a machine that can change its behavior based just on the initial information it has been given.
Latest Answers