Unrestricted Grammars and Turing Machines
It may be shown that unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar there exists some Turing machine capable of recognizing and vice-versa. Given an unrestricted grammar, such a Turing machine is simple enough to construct, as a two-tape nondeterministic Turing machine. The first tape contains the input word to be tested, and the second tape is used by the machine to generate sentential forms from . The Turing machine then does the following:
- Start at the left of the second tape and repeatedly choose to move right or select the current position on the tape.
- Nondeterministically choose a production from the productions in .
- If appears at some position on the second tape, replace by at that point, possibly shifting the symbols on the tape left or right depending on the relative lengths of and (e.g. if is longer than, shift the tape symbols left).
- Compare the resulting sentential form on tape 2 to the word on tape 1. If they match, then the Turing machine accepts the word. If they don't go back to step 1.
It is easy to see that this Turing machine will generate all and only the sentential forms of on its second tape after the last step is executed an arbitrary number of times, thus the language must be recursively enumerable.
The reverse construction is also possible. Given some Turing machine, it is possible to create an unrestricted grammar.
Read more about this topic: Unrestricted Grammar
Famous quotes containing the words unrestricted, grammars and/or machines:
“The unrestricted competition so commonly advocated does not leave us the survival of the fittest. The unscrupulous succeed best in accumulating wealth.”
—Rutherford Birchard Hayes (1822–1893)
“The violent illiteracies of the graffiti, the clenched silence of the adolescent, the nonsense cries from the stage-happening, are resolutely strategic. The insurgent and the freak-out have broken off discourse with a cultural system which they despise as a cruel, antiquated fraud. They will not bandy words with it. Accept, even momentarily, the conventions of literate linguistic exchange, and you are caught in the net of the old values, of the grammars that can condescend or enslave.”
—George Steiner (b. 1929)
“As machines become more and more efficient and perfect, so it will become clear that imperfection is the greatness of man.”
—Ernst Fischer (1899–1972)