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.
Max Maxfield 11/12/2012 2:19:11 PM User Rank Blogger
Re: "The thing is that, when it comes to Turing machines, you are limited only by your imagination"
@Crusty -- I cannot wait to hear what you think when you read thsi book -- for me it was close to a life-changing experiance in that it made me look at things from such a different perspective -- you'll see what I mean when you read it
Re: "The thing is that, when it comes to Turing machines, you are limited only by your imagination"
@Max I will get a copy from the library. I have to say this is why I like this site.
The contributors have such a varied background,that a new area of fascination is always just around the corner.
Oh so long ago, I got into hot water at college for doubting the Central Dogma on DNA, as it was then known.
I dared to say that the structure as defined by Xray crystallography would not be the same shape in the cell. The only tutor that stood up for me, was my Physical & Chemistry lecturer. He suggested I would be better off in Physics and Electronics, which is why you all now have to put up with me and my slow progress with FPGA implementation.
Max Maxfield 11/12/2012 10:38:35 AM User Rank Blogger
Re: "The thing is that, when it comes to Turing machines, you are limited only by your imagination"
@Rfindley: I couldn;t have answered this better myself. When I first heard the term "Junk DNA" years and years ago I thought "Let's not be too hasty here" -- and as you say they subsequently realized that very little of the DNA is not used for something (and even the bits that we don't think are used at the moment may turn out to do something really clever when we learn more).
And then there's the whole thing about the Epigenome -- that completely blew me away. We always think of evolution as being a very long, slow process, but now we know that there's a mechanism for characteristics to be changed from one generation to another. The following is from a blog I wrote a couple of years ago on this topic:
------------------ Stuff from a previous blog follows------------
I love this stuff, which explains why I found the article "Why Genes Aren't Your Destiny" (which appeared in the January 18th 2010 issue of Time magazine) to be so incredibly amazing, because it explains how complex beasts like ourselves can evolve in as quickly as a single generation.
Here's a question for you. We all know that every cell in our body contains the same DNA, so why are individual cells so different (skin cells, muscle cells, nerve cells, etc.)? The answer is a collection of "molecular switches" called epigenetic marks that are attached to the DNA. These switches, which cause different genes to turn on or off, conceptually sit "on top" of the genome (hence the prefix "epi" meaning "above").
The point of all this is that there's long been a debate as to the relative importance of "nature versus nurture", which provides a convenient catch-phrase for the roles played by heredity and environment in human development. The new field of epigenetics goes beyond this – we now know that lifestyle choices like smoking and eating too much can change our epigenetic marks, thereby affecting the way in which our genes express themselves.
More importantly, these changes in our epigenome can be passed down to our children and to their children. And how much do we really know and understand about all of this? The answer at this time is almost nothing. Remember the Human Genome Project? This determined that the human genome contains around 25,000 genes, and we know (or rather we don't know) just how complex this is. Well, if we visualize the genome as a drop of water, then we can visualize the relative complexity of the epigenome as being a mug of water (analogies are always suspect ... this one is doubly so because I just made it up, but you get my drift).
Can we harness the power of epigenetics for good (or will we mess things up like usual)? I tell you what, you should read the full article and then let's put our heads together and ponder the possibilities (you can read the full article online at the Time website, although for some reason the online version has a slightly different title to the print version: Why Your DNA Isn't Your Destiny).
Max Maxfield 11/12/2012 10:24:47 AM User Rank Blogger
Re: "The thing is that, when it comes to Turing machines, you are limited only by your imagination"
@Aser: Hi there -- welcome to the community -- re your comment about basing a 2D version of the Game of Life on a PicoBlaze -- did you see the articles about implementing it with each cell being its own state machine (click here for more details)
Re: "The thing is that, when it comes to Turing machines, you are limited only by your imagination"
>> The most of DNA code is usually corrupted and useless.
That was once the prevailing opinion, but man's wisdom has since been humbled. While only small sections appear to code for complete proteins, this is because DNA makes extensive use of lock-and-key methods to make sure that the right proteins are created at the right time. When the body (or development cycle in general) determines that it is the right time to produce a protein, a particular 'key' protein is created which has the right shape to wrap the RNA strand so that it brings together previously separated fragments of code. This 'unlocks' the sequence, allowing new proteins to be created.
Even the 'whitespace' regions are used. One example: they provide the right distance between code fragments for the above-described lock-and-key system to function properly. If you move a fragment of code that is surrounded by whitespace, that code fragment can no longer join (at the proper time) with its other corresponding fragments, because the 'key' no longer fits the lock.
There are also cases where scientists thought certain protein sequences were unused leftovers from evolution (because the corresponding proteins are not found in the body)... only to discover that these protein sequences are unlocked in the right environmental conditions. This came from studies of species in different climates, where genes were expressed in one climate, but not another. When a warm-climate critter was moved to a cold climate, it began to express the dormant gene of its cold-weather cousins.
So, the more we learn, the more we find that very little, if anything, is wasted in DNA.
To save this item to your list of favorite All Programmable Planet content so you can find it later in your Profile page, click the "Save It" button next to the item.
If you found this interesting or useful, please use the links to the services below to share it with other readers. You will need a free account with each service to share an item via that service.
Tweet This
