CSC 341: April 2, 2007

From CSWiki

Instructor's notes for the class session

The Turing-machine model of computation provides such good resources for simulation that it is possible to construct a universal Turing machine -- one that simulates the operation of any Turing machine $M$ on any input $w$ , given the encoding $\langle M, w\rangle$ . The simulation is so exact that non-termination is faithfully reproduced -- if $M$ never halts on input $w$ , then the universal Turing machine never halts on input $\langle M, w\rangle$

Just as the existence of the partial recursive function apply pointed up the need for the predicate defined?, so the availability of a universal Turing machine points up the need for a Turing machine that determines whether a given Turing machine $M$ halts on input $w$ . This halting machine would take $\langle M, w\rangle$ as its input, accepting if $M$ halts on $w$ and rejecting if not. In other words, a halting machine would solve the halting problem.

In recursive function theory, this line of inquiry led to the somewhat disappointing discovery that defined? is not partial recursive. Similarly, we find that the halting problem is not solvable -- there is no Turing machine that behaves as described. If you accept the Church-Turing thesis, it follows that no algorithm can determine, in general, whether $M$ halts on input $w$ .

Here is the proof. If there were a Turing machine $H$ that solved the halting problem, then we could use it to construct the following Turing machine $N$ :

$N =$ "On input $\langle M\rangle$ , where $M$ is a Turing machine:

Use $H$ to determine whether $M$ halts on input $\langle M\rangle$ .
If $H$ rejects, accept; otherwise, proceed to step 3.
Repeat step 3."

It is clear from this description that $N$ halts on input $\langle M\rangle$ if, and only if, $M$ does not halt on input $\langle M\rangle$ . But then what happens if $N$ is given its own encoding $\langle N\rangle$ as input? $N$ halts on input $\langle N\rangle$ if, and only if, $N$ does not halt on input $\langle N\rangle$ . Since this is impossible, $N$ cannot exist, and so either can $H$ . No Turing machine decides the halting problem.

On the other hand, the halting problem, considered as a language, is Turing-recognizable. One recognizer $R$ can be derived easily from the universal Turing machine, $U$ :

$R =$ "On input $\langle M, w\rangle$ , where $M$ is a Turing machine and $w$ is a string:

Run $U$ on $\langle M, w\rangle$ .
If and when $U$ accepts or rejects, accept."

Thus the halting problem shows that the set of Turing-decidable languages is a proper subset of the set of Turing-recognizable languages. One might hope, then, that all languages, even those that cannot be decided by Turing machines, could at least be recognized by Turing machines, so that we would at least have an algorithm for confirming that a given string is a member of the language in cases where this is, in fact, the case.

Alas, it turns out that not all languages are Turing-recognizable, either. Indeed, there is a simple cardinality argument showing that almost all languages are not Turing-recognizable: The number of languages is uncountable (i.e., there are more languages than natural numbers), but the number of Turing machines is countable, since each one can be fully described by a finite string in a finite alphabet.

We might still hope that, even though many non-Turing-recognizable languages exist, they are so obscure and bizarre that we will never encounter them in practice. Alas, this hope is also dashed immediately: The complement of the halting problem is a language that is easily described formally, but is not even Turing-recognizable. (If it were, then a Turing machine could run the recognizer for it in parallel with $R$ and thereby decide the halting problem.)

Our textbook runs through essentially the same line of inquiry, using the acceptance problem for Turing machines, $A_\mathrm{TM} = \{\langle M, w\rangle \mid M \textrm{\ is\ a\ Turing\ machine\ that\ accepts\ } w\}$ . This language is also Turing-recognizable but not Turing-decidable, and its complement is not Turing-recognizable. (The proof that $A TM$ is not Turing-decidable is that, if it were, it would be possible to use the decider for it in a machine that accepts $M$ if, and only if, $M$ does not accept $\langle M\rangle$ ; such a machine could neither accept nor fail to accept its own encoding and so cannot exist.)

The exercises and problems at the end of chapter 4 give a lot of examples of decidable languages and give you a feel for the ways in which Turing-decidability can be demonstrated. There are also some useful closure properties: The class of Turing-decidable languages is closed under union, complementation, intersection, concatenation, star, and many other convenient operations. The class of Turing-recognizable languages is closed under union, concatenation, and star, but not (as we have seen) under complementation. Unlike the class of context-free languages, however, it turns out that the class of Turing-recognizable languages is closed under intersection (one can simply run the recognizers for the intersected languages serially, starting the second if and when the first accepts).

[edit]

Study questions

1. Suppose that we try to construct a decider $D$ for $A TM$ on the following plan:

$D =$ "On input $\langle M, w\rangle$ where $M$ is a Turing machine and $w$ is a string:

Simulate the execution of $M$ on input $w$ .
If $M$ accepts, accept; otherwise, reject.

Why won't this work?

2. Prove that there is a language that is neither Turing-recognizable nor co-Turing-recognizable.

3. Prove that the class of Turing-recognizable languages is closed under reversal (that is, that if $L$ is Turing-recognizable, then $\{w^\mathcal{R} \mid w \in L\}$ is Turing-recognizable).

[edit]

Proposed Solutions

Since M is nowhere guaranteed to be a decider, it is possible that M will run forever on w. When this happens, D will also run forever, and therefore is not a decider.
$E Q T M$ is such language. (Theorem 5.30)
Suppose L is Turing-recognizable

Let $M L$ be a TM that recognizes it.

          _________________________________________
         |                                         | 
         |   __________           ___________      | 
         |  |          |         |           |     | 
  -- $w R$ --|->|  reverse |---- $w$ --->|     $M L$     |-----|--accept/reject---> 
         |  |__________|         |___________|     | 
         |_________________________________________|

Then $\{ w^{R} | w\in L \}$ is Turing-recognizable.

Previous Lecture Next Lecture

Front Door

Retrieved from "http://wiki.cs.grinnell.edu/mediawiki/index.php/CSC_341:_April_2%2C_2007"

CSC 341: April 2, 2007

From CSWiki

Instructor's notes for the class session

Study questions

Proposed Solutions

Views

Personal tools

Navigation

Search

Toolbox