CSC 341: March 12, 2007
From CSWiki
Instructor's notes for the class session
Although there are uncountably many languages that no Turing machine recognizes, it is surprisingly difficult to find them. Most problems that can be stated formally at all can be solved by Turing machines, including all of the languages that Sipser mentions in chapters 0, 1, and 2. As we learn in section 3.3, however, some problems that occur naturally in common contexts (such as "Does this polynomial have any integral roots?") aren't Turing-decidable.
It's natural, therefore, to look for ways of extending the design of Turing machines to make them more powerful, as we extended finite automata to get pushdown automata and pushdown automata to get Turing machines. Our textbook explores four of these: (1) adding a "stay put" tape-movement action; (2) adding more tapes, each with a separately movable read-write head; (3) using a nondeterministic model; and (4) attaching an external printer and redefining the criterion of acceptance to be presence on the printed list.
It turns out, however, that each of these extended models defines exactly the same class of languages as the simple Turing-machine model -- no new languages are recognizable in any of the extended models. Many other extensions have also been proposed: multitrack tapes, tapes that extend infinitely in both directions, two- or n-dimensional storage devices (with read-write heads that can move in four or 2n directions instead of just two), random-access memories, richer instruction sets, multiple processors, quantum devices, etc. None of these extensions affects the class of recognizable languages, since it turns out that in every case the extended automaton can be simulated by a simple Turing machine.
The simple Turing machine model, in fact, turns out to be an amazingly good environment for simulation. It can simulate any of the models of computation we've discussed up to this point, even the nondeterministic ones (using, for instance, the breadth-first search technique described in Sipser's proof of Theorem 3.16).
To simulate the model developed in our recursive function theory handout, it's convenient to adjust our perspective on the simple Turing-machine model, allowing more than one input to be written on the tape at the beginning of processing and recovering the value of a function from the tape when the machine halts. For the Turing machines that we'll use in the simulation, let's say that our input alphabet is always 
, that each numerical argument xi is initially recorded on the tape as the string 
followed by a terminating blank, and let's require that a conforming machine cannot halt unless it has removed all non-blank symbols from its tape except a string of 1s at the left end of the tape, and has returned the read-write head to the left end of the tape. The length of the string of 1swhen the machine halts encodes the value of the function.
It is easy to see that, for every primitive function from the handout, there is a Turing machine that computes that function and meets all the additional constraints. (The zero Turing machine, started on a blank tape, halts immediately. The successor Turing machine scans rightwards until it finds a blank, writes a 1 into that cell, then scans leftwards until it reaches the beginning of the tape again. A Turing machine computes a projection function by scanning once over all the inputs, erasing all except the one that the projection function will return, and then shifting the surviving input to the left end of the tape.)
Modelling composition, recursion, and unbounded minimization are somewhat trickier, but require only some care about keeping copies of the original inputs and leaving enough space for additional storage at key points in the simulation. The key insight is that we can protect an arbitrarily large region at the left end of the tape from being overwritten during a subcomputation by placing a divider symbol to its right, copying the inputs to the subcomputation to the right of the divider, and then performing the subcomputation on the part of the tape to the right of the divider, treating the divider as a sentinel, as if it marked the left end of the tape, during the subcomputation.
- In composition, we use the protected storage to keep copies of the original inputs and the values of the g-functions as we compute them, one by one; once they are all computed, we erase the original inputs, position the divider to the left of the g-function values, and apply the f-function.
- In recursion, we use the protected storage to keep copies of the original inputs and the value of a counter variable, applying the base function originally and then the step function repeatedly until the counter equals the last input.
- In unbounded minimization, we use the protected storage to keep copies of the original inputs and the value of a counter variable.
In this way, every partial recursive function is simulated by a Turing machine that meets our additional constraints. It is easy to covert any Turing machine that meets these constraints into one that halts in qaccept if the cell under the read-write head at the end contains a 1 and in qreject if that cell is blank, so it is clear that every primitive recursive set is Turing-decidable.
Study questions
- An off-line Turing machine has two tapes. One, which initially contains the input, is readable but not writable; the machine's finite control can move the reading head left or right and can use the symbol under the reading head to help select transitions, but cannot change the contents of the input tape. The other is a "scratch" tape that the machine can read, write, and move back and forth. Show that a language is Turing-recognizable if, and only if, it can be recognized by an off-line Turing machine.
- Show that every context-free language is Turing-decidable.
- Show that the set of Turing-decidable languages is closed under complementation.
Proposed Solutions
- To prove that a language is Turing-recognizable if, and only if, it is recognizable by an off-line Turing machine, we will show that standard Turing machines and off-line Turing machines are equivalent in power. A Turing machine may simulate an off-line Turing machine by finding the end of its input on the input tape, and marking the first empty cell with a divisor symbol not used elsewhere. It then runs without modifying the tape to the left of the divider symbol, using the tape to the right of the divider as its scratch tape. Similarly, an off-line Turing machine may simulate a regular Turing machine by copying the contents of the input tape to the scratch tape, and then running on the scratch tape exactly how a regular Turing machine would on its single tape.
- This study question is actually the same as Theorem 4.9 in the book that shows that "Every context-free language is decidable."
- Let L be a language that is decidable by the TM M. We can construct
to recognize 
by including M as a subroutine in , and accepting whenever M rejects, and rejecting whenever M accepts. Therefore, the set of Turing-decidable languages is closed under complementation.
