6.23. Turing Machines: Advanced Topics¶
6.23.1. Making More Complicated Machines¶
Obviously, Turing Machines can take an input and modify it. We will see examples of how this leads to powerful computational capability, even if it does not seem yet like they are so powerful. To get a quick idea of their power, consider the following relatively simple machine to accept \(L(a^nb^nc^n)\). This is significant, because this language is in fact not context free. Which means that this simple Turing Machine is doing something that no DFA, NFA, or PDA can do!
6.23.2. Unrestricted and Context Sensitive Grammars¶
Turing machines clearly can accept more languages than can PDAs, and therefore more than the Context Free Languages. Is there a class of grammars to match? Or at least, one or more classes of more powerful classes of grammars? Here we will briefly introduce two such classes of grammars.
Unrestricted Grammars allow productions \(u \rightarrow v\) where \(u\) is in \((V \cup T)^+\) and \(v\) is in \((V \cup T)^*\). In other words, an unrestricted grammar allows any combination of variables and terminals on both the left- and right-hand sides. The single restriction is that \(\lambda\) may not be the LHS of a rule. (So the term “unrestricted” is not literally true, but close!)
Context Sensitive Grammars are slightly more restrictive. A grammar is a CSG if all productions are of the form \(u \rightarrow v\) where \(u, v \in (V \cup T)^+\) and \(|u| \leq |v|\). Thus, a CSG cannot contract the number of things in any sentential form created during a derivation. In other words, while something created during a derivation can change its form (even a terminal can be changed), that work cannot disappear completely.
To illustrate their power, consider the following CSG.
This grammar generates the language \(L = \{ a^nb^nc^n : n \geq 1\}\). This is probably not an easy thing to recognize, nor an easy thing to come up with this grammar in the first place. CSG are quite hard to use. But try creating a derivation of a string for yourself. You should discover that the variables A and B are being used to control generation of the terminals a, b, and c to make sure that they stay balanced.
While there are some subtle distinctions between the power of CSGs and Unrestricted Grammars, we will simply say that the set of languages that can be generated by some Unrestricted Grammar is the same as the set of languages that can be recognized by some Turing machine. In contrast, the set of languages that can be generated by some CSG is the same as the set of languages that can be recognized by some Turing machine with certain restrictions on the amount of memory that it is permitted to use.
6.23.3. Simple Arithmetic… and Beyond¶
Previously we mentioned that a useful approach to representing numbers in a Turing machine is to use unary notation. In other words, the value \(n\) is represented by \(n\) marks (we will use the symbol 1). We showed a simple machine that implemented the increment function: Beginning at the start of the input number, move to the right until the first space is found and change that to ‘1’.
Now that we have seen implementations for copy and shift machines, we can easily see how to implement some simple mathematical functions. Adding two numbers represented in unary notation simply requires moving over the first number until the ‘1’ after the first space is found, and then shifting the next number to the right (to make it be part of the first number). This should give you a sense of why we prefer unary notation to binary or some other base. Imagine implementing binary number addition using a Turing machine! It is certainly possible, but would be a bit tedious to work out. Of course, the original computer developers had to do something similar.
Multiplication is slightly more complicated. Again, this would be represented by two blocks of 1’s. To do multiplication, we would first make a copy of the second operand to its right. We would then erase the first mark of the first operand. We would then repeat extending the length of our output by the length of the second operand. We would then reduce the length of the first operand by one. We would then repeat this process until the first operand has been erased. We would then erase the original second operand, move the head to the right of the output, and halt.
With enough effort, we could build up a full library of mathematical operations.
6.23.4. Turing’s Thesis and Algorithms¶
You now have some intuition for what can be accomplished by Turing machines. A Turing machine can act as a language acceptor, or as a transducer (meaning it can convert one string to another). We have also shown some simple mathematical computations. While it might be painful to write in “Turing machine code”, it is certainly possible. We have also seen how we can build up more complicated functionality. Conceptually at least, we have discussed how to reuse machines to make more advanced functionality easier to program.
How far can this go? In principle, as far as any computer. We will not present any further proof or argument here for this claim, other than to say that at their heart, computer programs are built on a few simple primitives like sequence, branches, and loops. The rest is just convenient syntax. These constructs can be implemented on Turing machines.
Turing’s Thesis: Any computation that can be carried out by mechanical means can be performed by some Turing machine.
From this, we have a useful working definition for the term algorithm: An algorithm to compute a function is a Turing machine program that solves it. Using this definition lets us reason formally about what problems (functions) do or do not have algorithms.
Later we will discuss some functions that proveably do not have an algorithm. For convenience, we will not present the argument in terms of Turing machines. But this was the original purpose for developing the Turing machine concept. One of the more startling conclusions is that a Turing machine can be implemented that takes a Turing machine representation as input and simulates its execution on an input string!
