Oh dear, oh dear, oh dear. Did you see All Programmable Planet blogger Jason's recent column on Turing Machines and their relevance to modern computing? Anyone who knows me at all knows that I have a Pavlovian response and my mind starts racing with ideas whenever I hear the words "Turing Machine."
As Jason says, a Turing machine is something that uses very simple rules to perform its computations. As originally conceived, Turing machines are not physical objects but mathematical ones. Having said this, lots of folks have constructed some jolly interesting physical realizations. For example, may I be so bold as to suggest that you glance over a couple of columns containing videos that I posted on the EE Times Programmable Logic Designline Website: One-bit processor and a mega-cool Turing Machine and A treasure-trove of tasty Turing Machines.
As soon as I saw these incredible implementations, I started to think about building my own machine, so it was a tad embarrassing when I suddenly came to the realization that I no longer had a clue as to how these little rascals actually worked. This was one of those occasions where I did know this stuff once, but the nitty-gritty details have faded from my mind as the sands of time have slithered their way through the hourglass.
Thus it was that I decided to work things out from first principles as follows... In his original thought experiment, Turing imagined a machine that is "looking at" a paper tape that is infinitely long in each direction. The machine can read the value on the paper tape at its current location (this value could be a blank or a '0' or a '1'). The machine can modify this value if it wishes, and it can then move the tape one position to the left or right.
The way the Turing machine works is as a finite-state machine (FSM). Basically, you decide what program you wish to perform and you create a state machine to implement it. On this basis, we can have as many states as we wish -- let's call them S0, S1, S2... Sn. The actions our machine can perform are depicted in the following table:
We commence in some current state, Snow (this is one of our S0, S1... states), which will be stored in a set of state variable registers. The machine reads the value on the tape at the current position. This value may be 'B' (Blank), '0,' or '1'; the '--' entry in this column of the table indicates that we may simply not care what the value on the tape is. For each of the different possible existing values on the tape, we may decide to write a new value at this position. This new value may be 'B' (Blank, which means to clear this location), '0,' or '1'; alternatively, we may not wish to write anything at this time, which equates to the '--' entries in this column of the table.
Next, we perform a move operation 'N' (None), 'L' (one place left), or 'R' (one place right). Finally, we load our state variables with some new state, Snew (one of our S0, S1... states), which could be different for each row in the above table, and then we do the whole thing again. Of course, the table shown above offers only a high-level generic view. For a real implementation, we would expand the table out to explicitly describe the actions of each state and transition between states.
Next page >