I’ve been thinking about Turing machines a lot, and doing some reading about them. The basic explanation, if I can remember it: there’s a machine that can read this paper tape (probably mylar if it was invented now). The tape looks sort of like a piece of movie film or something, and each square can hold a 1 or a 0. The machine can also move the tape left or right, to read another square. The machine has in internal state, which is basically like one memory location that holds a number. The machine is also constructed to follow a ruleset. The ruleset is a bunch of if-then statements that distate tape movement and the storage of new items on the tape. So, “if the tape says 0 and the current state is 20, change the current state to 27, write a 1 in this position, and move the tape left”
What the hell does all this mean? Turing designed this thing (on paper) in 1936 as the solution to a problem about designing a machine that could solve any mathematical problem without being physically rebuilt or modified. This seems pretty stupid if you’ve got a pentium on your desk, but back then, it was a big deal. And if you’ve ever worked with assembly language, you know the similarities between a Turing machine and a simple (i.e. non-Intel) processor. A Turing machine is sort of like a one-register RISC processor, except it addresses a bunch of paper tape instead of a bus.