Instead of starting with the definition of a Turing machine and trying to persuade the reader that such a machine can be universal, we will start with a model that a reader can easily accept to be universal and then try to show that such a model is just a Turing machine when we look at it in the right perspective.
1. What do we do when we try to do a mathematical calculation? We have a text book to refer to and a note book to write in. In a certain state of mind we read some part of a page of the text book. What we read changes our state of mind. And then we could do one or all of the following: a) Make some calculations in our note book; b) go to the previous page in the text to renew our understanding of something we learned earlier; c) go to the next page in the text to continue our effort to understand how the calculation is done.
Surely that is all any one can do, right? So one can say that we have described a universal method of doing a mathematical computation.
2. Now let us change the setting slightly. Don't let the text book and the note book be separate entities. Suppose we have a workbook in which only a part of the page has text and the rest is left blank for us to do our working. If the blank space is not enough, we are free to add one or more additional sheets at that point to help us. Surely the model continues to be universal?
3. Now comes the crucial jump. Recall that the definition of a Turing machine only requires the tape alphabet to be a finite set. There is no limit set on how large it can be.
Take a deep breath now. Can you think of the entire text and the blank space on the workbook as a single symbol from a set of finite symbols? And the entire page of the work book with all the additional sheets attached as a single square?
Don't we have a Turing machine then?
Monday, March 30, 2009
Sunday, March 22, 2009
Turing Machines - 1
In the way it is usually defined a Turing machine has an infinite tape for storage. This storage tape serves also as the input device and the output device.
Even though the tape is infinite it is to be noted that the definition specifically mentions that all except a finite number of squares are blank. This means that a TM is actually dealing with a finite string. We could have a finite string with two end of the line symbols and arrange matters so that if the reading head happens to see one of them it simply moves it one square away. See the Book for a detailed definition along these lines.
But if a TM actually deals with finite but arbitrarily long strings, just like finite automata, then how is it that a TM can be universal? The reason is the ability of the head of the TM to move both forward and back and change the symbols it encounters.
In the next post I will attempt a simple argument that shows that a TM is "naturally and obviously" universal.
Even though the tape is infinite it is to be noted that the definition specifically mentions that all except a finite number of squares are blank. This means that a TM is actually dealing with a finite string. We could have a finite string with two end of the line symbols and arrange matters so that if the reading head happens to see one of them it simply moves it one square away. See the Book for a detailed definition along these lines.
But if a TM actually deals with finite but arbitrarily long strings, just like finite automata, then how is it that a TM can be universal? The reason is the ability of the head of the TM to move both forward and back and change the symbols it encounters.
In the next post I will attempt a simple argument that shows that a TM is "naturally and obviously" universal.
Subscribe to:
Posts (Atom)