Microsoft Word – Solutions_TuringMachines.doc
Chapter 17 1
Part IV: Turing Machines and Undecidability
17 Turing Machines
1) Give a short English description of what each of these Turing machines does:
a) SM = {a, b}. M =
Shift the input string one character to the right and replace each b with an a and each a with a b.
b) SM = {a, b}. M =
Erase the input string and replace it with a count, in unary, of the number of a’s in the original string.
2) Construct a standard, one-tape Turing machine M to decide each of the following languages L. You may find it
useful to define subroutines. Describe M in the macro language described in Section 17.1.5.
a) {x * y = z : x, y, z Î 1+ and, when x, y, and z are viewed as unary numbers, xy = z}. For example, the string
1111*11=11111111 Î L.
Chapter 17 2
�Check for legal form | Check for legal arithmetic
>R R¬1 R R¬1 R R¬1 L❑ R # R* R¬% % R= R¬! ! L*
1 * 1 = 1 ❑ 1 1
¬1 ¬* ¬1 ¬= ¬1 ¬❑ = ❑
n n n n n n L 1 n
%
*
L# R R= R❑,1 y
* ❑
1
1
n
b) {aibjcidj, i, j ³ 0}.
c) {w Î {a, b, c, d}*: #b(w) ³ #c(w) ³#d(w) ³ 0}.
3) Construct a standard 1-tape Turing machine M to compute each of the following functions:
a) The function sub3, which is defined as follows:
sub3(n) = n-3 if n > 2
0 if n £ 2.
Specifically, compute sub3 of a natural number represented in binary. For example, on input 10111, M
should output 10100. On input 11101, M should output 11010. (Hint: you may want to define a
subroutine.)
We first define a subroutine that we will call S to subtract a single 1:
> R❑ L 1
0
❑
1
0 L R ❑
❑
¬❑
0 R ❑
¬❑
❑ L❑
L❑
Now we can define M as: > S S S
b) Addition of two binary natural numbers (as described in Example 17.13). Specifically, given the input
string
Chapter 17 3
a natural number y, M should output
101;11, M should output 1000.
c) Multiplication of two unary numbers. Specifically, given the input string
unary encoding of a natural number x and
output
111111111111.
>R 1 ❑ R 1 ❑ R; R 1 2 R❑ 3 L2
; ; 3 ❑
❑ R 1 ❑ ❑ L; R 2 1 L; ❑
❑ ❑,3
h L; L❑
❑
R3,❑ 1
3
This machine first erases the first 1 in x. Then it uses each of the others to create a new copy of y. Each
time it uses a 1 in x, it writes over it with a blank. Once all the ones in x have created their copies of y, the ;
is erased.
d) The proper subtraction function monus, which is defined as follows:
monus(n, m) = n – m if n > m
0 if n £ m
Specifically, compute monus of two natural numbers represented in binary. For example, on input
101;11, M should output 10. On input 11;101, M should output 0.
4) Define a Turing Machine M that computes the function f: {a, b}* ® N, where:
f(x) = the unary encoding of max(#a(x), #b(x)).
For example, on input aaaabb, M should output 1111. M may use more than one tape. It is not necessary to
write the exact transition function for M. Describe it in clear English.
We can use 3 tapes: Tape 1: input
Tape 2: write 1 for every a in the input
Tape 3: write 1 for every b in the input
• Step 1: Move left to right along tape 1. If the character under the read head is a, write 1 on tape 2 and
move one square to the right on tapes 1 and 2. If the character under the read is b, write 1 on tape 3
and move one square to the right on tapes 1 and 3. When tape 1 encounters a blank, go to step 2.
• Step 2: Move all three read heads all the way to the left. Scan the tapes left to right. At each step, if
there is 1 on either tape 2 or 3 (or both), write 1 on tape 1. Move right on all tapes except that as soon
as either tape 2 or tape 3 (but not both) gets to a blank, stop moving right on that tape and continue this
Chapter 17 4
process with just the other one. As soon as the other of them (tape 2 or 3) also hits a blank, go to step
3. At this point, tape 1 contains the correct number of 1’s, plus perhaps extra a’s and b’s that still
need to be erased.
• Step 3: Scan left to right along tape 1 as long as there are a’s or b’s. Rewrite each as a blank. As soon
as a blank is read, stop.
5) Construct a Turing machine M that converts binary numbers to their unary representations. So, specifically, on
input
tape.)
M will use three tapes. It will begin by copying its input to tape 2, where it will stay, unchanged. Tape 1
will hold the answer by the end. Tape 3 will hold a working string defined below. M will initialize itself
by copying its input to tape 2 and writing 1 on tape 3. Then it will begin scanning tape 2, starting at the
rightmost symbol, which we’ll call symbol 0. As M computes, tape 3 will contain 1i if M is currently
processing the ith symbol (from the right, starting numbering at 0). Assume that M has access to a
subroutine double that will duplicate whatever string is on tape 3. So if that string is s, it will become ss.
After initialization, M operates as follows:
For each symbol c on tape 2, do:
1. If c = 1, then append a copy of the nonblank region of tape 3 to the end of the nonblank region of
tape 1. (If this is the first append operation, just write the copy on the tape where the read/write
head is.)
2. Call double.
3. Move the read head on tape 2 one square to the left.
4. If the square under the read/write head on tape 2 is ❑, halt. The answer will be on tape 1.
14) Encode the following Turing Machine as an input to the universal Turing machine:
M = (K, S, G, d, q0, {h}), where:
K = {q0, q1, h},
S = {a, b},
G = {a, b, c, ❑}, and
d is given by the following table:
q s d(q, s)
q0 a (q1, b, ®)
q0 b (q1, a, ®)
q0 ❑ (h, ❑ , ®)
q0 c (q0, c, ®)
q1 a (q0, c, ®)
q1 b (q0, b, ¬)
q1 ❑ (q0, c, ®)
q1 c (q1, c, ®)
We can encode the states and the alphabet as:
q0 q00
q1 q01
h q10
a a00
b a01
❑ a10
c a11
Chapter 17 5
We can then encode d as:
(q00,a00,q01,a01,®),(q00,a01,q01,a00,®),(q00,a10,q10,a10,®),
(q00,a11,q00,a11,®),(q01,a00,q00,a11,®),(q01,a01,q00,a01,¬),
(q01,a10,q00,a11,®),(q01,a11,q01,a11,®)
Chapter 19 6
19 The Unsolvability of the Halting Problem
1) Consider the language L = {
a) Describe in clear English a Turing machine M that semidecides L.
M generates the strings in åM* in lexicographic order and uses dovetailing to interleave the computation of
M on those strings. As soon as two computations accept, M halts and accepts.
b) Suppose we changed the definition of L just a bit. We now consider:
L¢ = {
Can you tweak the Turing machine you described in part a to semidecide L¢?
No. M could discover that two strings are accepted. But it will never know that there aren’t any more.
2) Consider the language L = {
a) Describe in clear English a Turing machine M that semidecides L.
On input
1. Run M on 10. If it rejects, loop.
2. If it accepts, run M on 11. If it rejects, loop.
3. If it accepts, run M on 101. If it accepts, accept. Else loop.
This procedure will halt and accept iff M accepts the binary encodings of the first three prime numbers. If,
on any of those inputs, M either fails to halt or halts and rejects, this procedure will fail to halt.
b) Suppose (contrary to fact, as established by Theorem 19.2) that there were a Turing machine Oracle that
decided H. Using it, describe in clear English a Turing machine M that decides L.
On input
1. Invoke Oracle(
2. If M would not accept, reject.
3. Invoke Oracle(
4. If M would not accept, reject.
5. Invoke Oracle(
6. If M would accept, accept. Else reject.
7
20 Decidable and Semidecidable Languages
1) Show that the set D (the decidable languages) is closed under:
a) Union
b) Concatenation
c) Kleene star
d) Reverse
e) Intersection
All of these can be done by construction using deciding TMs. (Note that there’s no way to do it with
grammars, since the existence of an unrestricted grammar that generates some language L does not tell us
anything about whether L is in D or not.)
a) Union is straightforward. Given a TM M1 that decides L1 and a TM M2 that decides L2, we build a TM
M3 to decide L1 È L2 as follows: Initially, let M3 contain all the states and transitions of both M1 and M2.
Create a new start state S and add transitions from it to the start states of M1 and M2 so that each of them
begins in its start state with its read/write head positioned just to the left of the input. The accepting states
of M3 are all the accepting states of M1 plus all the accepting states of M2.
b) is a bit tricky. Here it is: If L1 and L2 are both in D, then there exist TMs M1 and M2 that decide them.
From M1 and M2, we construct M3 that decides L1L2. Since there is a TM that decides L3, it is in D.
The tricky part is doing the construction. When we did this for FSMs, we could simply glue the accepting
states of M1 to the start state of M2 with e transitions. But that doesn’t work now. Consider a machine that
enters the state y when it scans off the edge of the input and finds a blank. If we’re trying to build M3 to
accept L1L2, then there won’t be a blank at the end of the first part. But we can’t simply assume that that’s
how M1 decides it’s done. It could finish some other way.
So we need to build M3 so that it works as follows: M3 will use three tapes. Given some string w on tape 1,
M3 first nondeterministically guesses the location of the boundary between the first segment (a string from
L1) and the second segment (a string from L2). It copies the first segment onto tape 2 and the second
segment onto tape 3. It then simulates M1 on tape 2. If M1 accepts, it simulates M2 on tape 3. If M2
accepts, it accepts. If either M1 or M2 rejects, that path rejects.
There is a finite number of ways to carve the input string w into two segments. So there is a finite number
of branches. Each branch must halt since M1 and M2 are deciding machines. So eventually all branches
will halt. If at least one accepts, M3 will accept. Otherwise it will reject.
2) Show that the set SD (the semidecidable languages) is closed under:
a) Union
b) Concatenation
c) Kleene star
d) Reverse
e) Intersection
3) Let L1, L2, …, Lk be a collection of languages over some alphabet S such that:
• For all i ¹ j, Li Ç Lj = Æ.
• L1 È L2 È … È Lk = S*.
• “i (Li is in SD).
Prove that each of the languages L1 through Lk is in D.
“i (¬Li = L1 È L2 È …È Li-1 È Li+1 È …È Lk).
Each of these Lj’s is in SD, so the union of all of them is in SD. Since Li is in SD and so is its complement,
it is in D.
8
4) If L1 and L3 are in D and L1 Í L2 Í L3, what can we say about whether L2 is in D?
L2 may or may not be in D. Let L1 be Æ and let L3 be S. Both of them are in D. Suppose L2 is H. Then it
is not in D. But now suppose that L2 is {a}. Then it is in D.
5) Let L1 and L2 be any two decidable languages. State and prove your answer to each of the following questions:
a) Is it necessarily true that L1 – L2 is decidable?
Yes. The decidable languages are closed under complement and intersection, so they are closed under
difference.
b) Is it possible that L1 È L2 is regular?
Yes. Every regular language is decidable. So Let L1 and L2 be {a}. L1 È L2 = {a}, and so is regular.
6) Let L1 and L2 be any two undecidable languages. State and prove your answer to each of the following
questions:
a) Is it possible that L1 – L2 is regular?
Yes. Let L1 = L2. Then L1 – L2 = Æ, which is regular.
b) Is it possible that L1 È L2 is in D?
Yes. H È ¬H = {
7) Let M be a Turing machine that lexicographically enumerates the language L. Prove that there exists a Turing
machine M¢ that decides LR.
Since L is lexicographically enumerated by M, it is decidable. The decidable languages are closed under
reverse. So LR is decidable. Thus there is some Turing machine M¢ that decides it.
8) Construct a standard one-tape Turing machine M to enumerate the language:
{w : w is the binary encoding of a positive integer that is divisible by 3}.
Assume that M starts with its tape equal to ❑. Also assume the existence of the printing subroutine P, defined
in Section 20.5.1. As an example of how to use P, consider the following machine, which enumerates L¢, where
L¢ = {w : w is the unary encoding of an even number}:
> P R 1 R 1
You may find it useful to define other subroutines as well.
9
Define the subroutine A (Add1) as follows:
Input: ❑ w1 w2 w3 …wn ❑ (encoding some integer k)
Output: ❑ w1 w2 w3 …wm ❑ (encoding k+1)
> 0 L
1
0
❑
1 R❑ L
1 R❑ L
The enumerating machine M is now:
> R 0 A A A P
9) Construct a standard one-tape Turing machine M to enumerate the language AnBn. Assume that M starts with
its tape equal to ❑. Also assume the existence of the printing subroutine P, defined in Section 20.5.1.
>P L❑ a R❑ b
10
21 Decidability and Undecidability Proofs
1) For each of the following languages L, state whether it is in D, in SD/D, or not in SD. Prove your answer.
Assume that any input of the form
a) {a}.
D. L is finite and thus regular and context-free. By Theorem 20.1, every context-free language is in D.
b)
SD/D. Let R be a mapping reduction from H to L defined as follows:
R(< M, w>) =
1. Construct the description
follows:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept.
2. Return
If Oracle exists, then C = Oracle(R(
• R can be implemented as a Turing machine.
• C is correct: M# accepts everything or nothing, depending on whether M halts on w. So:
• < M, w> Î H: M halts on w, so M# accepts all inputs, including a. Oracle accepts.
• < M, w> Ï H: M does not halt on w, so M# accepts nothing. In particular, it does not accept
a. Oracle rejects.
But no machine to decide H can exist, so neither does Oracle.
c) {
¬SD: Let R be a reduction from ¬H = {
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. If x = a, accept.
1.2. Erase the tape.
1.3. Write w.
1.4. Run M on w.
1.5. Accept.
2. Return
If Oracle exists and semidecides L, then C = R(
•
Oracle accepts.
•
But no machine to semidecide ¬H can exist, so neither does Oracle.
11
d) {
¬SD. Let R be a reduction from ¬H = {
R(
1. Construct the description of M#(x) that operates as follows:
1.1. Erase the tape.
1.2. Write w.
1.3. Run M on w.
1.4. Accept.
2. Construct the description of M?(x) that, on input x, operates as follows:
2.1. Accept.
3. Return
If Oracle exists and semidecides L, then C = Oracle(R(
• R can be implemented as a Turing machine.
• C is correct: M? accepts everything, including e. M# accepts everything or nothing, depending on
whether M halts on w. So:
•
= L(M?), which contains e. So Oracle accepts.
•
So Oracle does not accept.
But no machine to semidecide ¬H can exist, so neither does Oracle.
e) {
¬SD.
f) {
¬SD. Let R be a reduction from ¬H = {
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. Erase the tape.
1.2. Write w.
1.3. Run M on w.
1.4. Accept.
2. Construct the description of M?(x) that, on input x, operates as follows:
2.1. Accept.
3. Return
If Oracle exists and semidecides L, then C = Oracle(R(
• R can be implemented as a Turing machine.
• C is correct: L(M?) = S*. M# accepts everything or nothing, depending on whether M halts on w.
So:
•
So Oracle accepts.
•
But no machine to semidecide ¬H can exist, so neither does Oracle.
g) {
D. Notice that M = (K, S, G, d, s, H) must move either to the right or the left on each move. If it cannot
move right on two consecutive moves, then every time it moves right, it must next move back left. So it
will never be able to read more than the first square of its input tape. It can, however, move left
indefinitely. That part of the tape is already known to contain only blanks. M can write on the tape as it
12
moves left, but it cannot ever come back to read anything that it has written except the character it just
wrote and the one immediately to its right. So the rest of the tape is no longer an effective part of M’s
configuration. We need only consider the current square and one square on either side of it. Thus the
number of effectively distinct configurations of M is max = |K| × |G|3. Once M has executed max steps, it
must either halt or be in a loop. If the latter, it will just keep doing the same thing forever. So the
following procedure decides L:
Run M on w for |K| × |G|3 +1 moves or until M halts or moves right on two consecutive moves:
• If M ever moves right on two consecutive moves, halt and reject.
• If M halts without doing that or if it has not done that after |K| × |G|3 +1 moves, halt and accept.
h) {
D. L = Æ, since any language that is accepted by some Turing machine is accepted by an infinite number
of Turing machines.
i) {
SD/D: The following algorithm semidecides L:
Run M on the strings in S* in lexicographic order, interleaving the computations. As soon as two
such computations have accepted, halt.
Proof not in D: R is a reduction from H = {
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M.
1.4. Accept.
2. Return
If Oracle exists and decides L, then C = Oracle(R(
•
accepts.
•
at least two strings so Oracle rejects.
But no machine to decide H can exist, so neither does Oracle.
j) {
SD/D: The following algorithm semidecides L:
Run M on the even length strings in S* in lexicographic order, interleaving the computations. As
soon as two such computations have rejected, halt.
Proof not in D: R is a reduction from H = {
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M.
1.4. Reject.
2. Return
13
If Oracle exists and decides L, then C = Oracle(R(
•
Oracle accepts.
•
least even length two strings. Oracle rejects.
But no machine to decide H can exist, so neither does Oracle.
k) {
¬SD: Assume that S ¹ Æ. R is a reduction from ¬H = {
as follows:
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. Save its input x on a second tape.
1.2. Erase the tape.
1.3. Write w.
1.4. Run M on w for |x| steps or until it halts.
1.5. If M would have halted, then loop.
1.6. Else halt.
2. Return
If Oracle exists and semidecides L, then C = R(
•
including all palindromes, so Oracle accepts.
•
M# loops at step 1.5. For any k, there is a palindrome of length greater than k. So M# fails to accept
all palindromes. So Oracle does not accept.
But no machine to semidecide ¬H can exist, so neither does Oracle.
l) {
¬SD. R is a reduction from ¬H = {
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. Save x.
1.2. Erase the tape.
1.3. Write w.
1.4. Run M on w.
1.5. If x Î AnBnCn, accept. Else loop.
2. Return
If Oracle exists and semidecides L, then C = Oracle(R(
•
So Oracle accepts.
•
accept.
But no machine to semidecide ¬H can exist, so neither does Oracle.
14
m) {
¬SD. R is a reduction from ¬H = {
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. If x Î AnBnCn, accept.
1.2. Erase the tape.
1.3. Write w.
1.4. Run M on w.
1.5. Accept.
2. Return
If Oracle exists and semidecides L, then C = Oracle(R(
•
context-free. So Oracle accepts.
•
But no machine to semidecide ¬H can exist, so neither does Oracle.
n) {
SD/D: The following algorithm semidecides L: Lexicographically enumerate the strings in a* and run
them through M in dovetailed mode. If M ever accepts a string, accept.
We show not in D by reduction: R is a reduction from H to L, defined as follows:
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1 Erase the tape.
1.2 Write w.
1.3 Run M on w.
1.4 Accept.
2. Return
If Oracle exists and decides L, then C = Oracle(R(
•
•
But no machine to decide H can exist, so neither does Oracle.
o) {
¬SD: Assume that S ¹ Æ. R is a reduction from ¬H = {
as follows:
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. If x is one of the first two strings (lexicographically) in S*, accept.
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w.
1.5. Accept.
2. Return
15
If Oracle exists and semidecides L, then C = R(
•
So |L(M#)| = 2, which is greater than 0 and prime, so Oracle accepts.
•
strings over any nonempty alphabet, so L(M#) is infinite. Its cardinality is not a prime integer. So
Oracle does not accept.
But no machine to semidecide ¬H can exist, so neither does Oracle.
p) {
SD/D: The following algorithm semidecides L:
Run M on the strings in S* of length less than |
computations. If any such computation halts, halt and accept.
Proof not in D: R is a reduction from H = {
R(
1. Construct the description
follows:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept.
2. Return
If Oracle exists and decides L, then C = Oracle(R(
•
of length less than |
•
is no string of length less than |
But no machine to decide H can exist, so neither does Oracle.
q) {
¬SD: R is a reduction from ¬H = {
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept.
2. Return
If Oracle exists and semidecides L, then C = R(
•
ends in 0. So Oracle accepts.
•
does accept strings that end in 0, M# is not in L and Oracle does not accept.
But no machine to semidecide ¬H can exist, so neither does Oracle.
16
r) {
s, and s < 1000 and s is prime}.
D. Note that in any fixed number s steps, M can examine no more than s squares of its tape. So if it is
going to accept any string w that is longer than s, it must also accept a string w¢ that is no longer than s and
that is an initial substring of w. So the following algorithm decides L:
Run M on all strings in S* of length between 0 and 1000. Try each for 1000 steps or until the
computation halts:
• If at least two such computations halted in some prime number of steps s, accept.
• Else reject.
s) {
D. In |
decides L:
Run M on all strings in S* of length between 0 and |
computation halts:
• If at least one such computation halted, accept.
• Else reject.
It isn’t necessary to try any longer strings because, if M accepts some longer string, it does so by looking at
no more than |
characters. And we’d have discovered that.
t) {
¬SD. Assume that S ¹ Æ. R is a reduction from ¬H = {
as follows:
R(
1. Construct the description of M#(x) that, on input x, operates as follows:
1.1. Save its input x on a second tape.
1.2. Erase the tape.
1.3. Write w.
1.4. Run M on w for |x| steps or until it halts.
1.5. If M would have halted, then loop.
1.6. Else accept.
2. Return Oracle(
If Oracle exists and semidecides L, then R semidecides ¬H:
•
is an infinte set. So Oracle accepts.
•
or greater. It accepts strings of length less than k. But that set is finite. So Oracle does not accept.
But no machine to semidecide ¬H can exist, so neither does Oracle.
u) {
D. L = Æ, since every Turing machine M = (K, S, G, d, s, H) accepts some subset of S* and |S*| is
countably infinite. So L is not only in D, it is regular.
17
7) Show that each of the following questions is undecidable by recasting it as a language recognition problem and
showing that the corresponding language is not in D:
a) Given a program P, input x, and a variable n, does P, when running on x, ever assign a value to n?
L = {
from H. Define:
R(
1. Construct the description
of a program P that ignores its input and operates as follows:
1.1. Erase a simulated tape.
1.2. Write w on the tape.
1.3. Simulate running M on w.
1.4. Set n to 0.
2. Return
If Oracle exists and decides L, then C = Oracle(R(
machine. And C is correct:
•
accepts.
•
Oracle(
But no machine to decide H can exist, so neither does Oracle.
b) Given a program P and code segment S in P, does P reach S on every input (in other words, can we
guarantee that S happens)?
c) Given a program P and a variable x, is x always initialized before it is used?
d) Given a program P and a file f, does P always close f before it exits?
e) Given a program P with an array reference of the form a[i], will i, at the time of the reference, always be
within the bounds declared for the array?
f) Given a program P and a database of objects d, does P perform the function f on all elements of d?
L = {
Define:
R(
1. Create a database D with one record r.
2. Create the function f that writes the value of the first field of the database object it is given.
3. Construct the description
of a program P that ignores its input and operates as follows:
3.1. Erase a simulated tape.
3.2. Write w on the tape.
3.3. Simulate running M on w.
3.4. Run f on r.
4. Return
18
If Oracle exists and decides L, then C = Oracle(R(
machine. And C is correct:
•
•
But no machine to decide H can exist, so neither does Oracle.
10) Do the other half of the proof of Rice’s Theorem, i.e., show that the theorem holds if P(Æ) = True.
The easiest way to do this is to use a reduction that is not a mapping reduction. We simply invert the
reduction that we did to prove the first half. So we proceed as follows. Assume that P(Æ) = True. Since P
is nontrivial, there is some SD language LF such that P(LF) is False. Since LF is in SD, there exists some
Turing machine K that semidecides it.
Define:
R(
1. Construct the description
follows:
1.1. Copy its input x to a second tape.
1.2. Erase the tape.
1.3. Write w on the tape.
1.4. Run M on w.
1.5. Put x back on the first tape and run K on x.
2. Return
{R, ¬} is a reduction from H to L2. If Oracle exists and decides L, then C = ¬Oracle(R(
H. R can be implemented as a Turing machine. And C is correct:
• If
L(M#) = L(K) and P(L(M#)) = P(L(K)). We chose K precisely to assure that P(L(K)) is False, so
P(L(M#)) must also be False. Oracle decides P. Oracle(
• If
Æ. By assumption, P(Æ) = True. Oracle decides P. Oracle(
But no machine to decide H can exist, so neither does Oracle.
11) For each of the following languages L, do two things:
i) State whether or not Rice’s Theorem has anything to tell us about the decidability of L.
ii) State whether L is in D, SD/D, or not in SD.
a) {
Rice’s Theorem applies and tells us that L is not in D. It is also true that L is not in SD.
b) {
Rice’s Theorem does not apply. L is in D. It can be decided by simply running M on e for 1000 steps or
until it halts.
c) ¬L1, where L1 = {
Rice’s Theorem does not apply. L1 is in D. The key to defining a decision procedure for it is the
observation that if M is allowed to run for only 1000 steps, it must make its decision about whether to
accept an input string w after looking at no more than the first 1000 characters of w. So we can decide L1
19
by doing the following: Lexicographically enumerate the strings of length up 1000 drawn from the
alphabet of M. For each, run M for 1000 steps or until it halts. If M halted on all of them, then it must also
halt on all longer strings. So accept. Otherwise, reject. Since the decidable languages are closed under
complement, ¬L1 must be in D if L1.
d) {
Rice’s Theorem does not apply. Note that the definition of this language does not ask about the language
that M accepts. Failure to reject could mean either that M accepts or that it loops. L is in SD.
12) Use Rice’s Theorem to prove that each of the following languages is not in D:
a) {
We define P as follows:
• Let P be defined on the set of languages accepted by some Turing machine M. Let it be True if
L(M) contains at least two odd length strings and False otherwise.
• The domain of P is the SD languages since it is those languages that are accepted by some Turing
machine M.
• P is nontrivial since P({a, aaa}) is True and P(Æ) is False.
Thus {
b) {
We define P as follows:
• Let P be defined on the set of languages accepted by some Turing machine M. Let it be True if
|L(M)| is 12 and False otherwise.
• The domain of P is the SD languages since it is those languages that are accepted by some Turing
machine M.
• P is nontrivial since P({a, aa, aaa, aaaa, aaaaa, aaaaaa, b, bb, bbb, bbbb, bbbbb,
bbbbbb}) is True and P(Æ) is False.
Thus {
20) If L1 and L2 are decidable languages and L1 Í L Í L2, must L be decidable? Prove your answer.
No. Let L1 = Æ. Let L2 = {
20
22 Undecidable Languages That Do Not Ask Questions
about Turing Machines
1) Consider the following instance of the Post Correspondence problem. Does it have a solution? If so, show one.
X Y
1 a bab
2 bbb bb
3 aab ab
4 b a
2, 1, 2 is a solution.
2) Prove that, if we consider only PCP instances with a single character alphabet, PCP is decidable.
If there is any index i such that Xi = Yi, then the single element sequence i is a solution.
If there is some index i with the property that |Xi| > |Yi| and another index j with the property that |Xj| < |Yj|
then there is a solution. In this case, there must be values of n, m, k, and p such that (giving the name a to
the single element of S):
X Y
i: …. an+k ….. an
j: am am+p
The sequence ip jk must be a solution since:
• the number of a’s in the X string will then be p(n+k)+km = pn + pk + km, and
• the number of a’s in the Y string will then be pn + k(m+p) = pn + kp + km.
For example, suppose that we have:
X Y
1: …. aaaaaaa aaa
2: aa aaaaaaa
We can restate that as:
X Y
1: …. a3+4 a3
2: a2 a2+5
So: n = 3, k = 4 m = 2, p = 5
So 1, 1, 1, 1, 1, 2, 2, 2, 2 is a solution:
X: …. a7a7a7a7a7a2a2a2a2 = a43
Y: a3a3a3a3a3a7a7a7a7 = a43
If, on the other hand, neither of these conditions is satisfied, there is no solution. Now either all the X
strings are longer than their corresponding Y strings or vice versa. In either case, as we add indices to any
proposed solutions, the lengths of the resulting X and Y strings get farther and farther apart.
21
3) Prove that, if an instance of the Post Correspondence problem has a solution, it has an infinite number of
solutions.
If S is a solution, then S2, S3, … are all solutions.
4) State whether or not each of the following languages is in D and prove your answer.
a) {
L is in D. L can be decided by the procedure:
If decideCFL(L, e) returns True, accept. Else reject.
b) {
L is in D. By the context-free pumping theorem, we know that, given a context-free grammar G, if there is
a string of length greater than bn in L(G), then vy can be pumped out to create a shorter string also in L(G)
(the string must be shorter since |vy| >0). We can, of course, repeat this process until we reduce the original
string to one of length less than bn. This means that if there are any strings in L(G), there are some strings
of length less than bn. So, to see whether L(G) = {e}, we do the following: First see whether e Î L(G) by
seeing whether decideCFL(L, e) returns True. If not, say no. If e is in L(G), then we need to determine
whether any other strings are also in L(G). To do that, we test all strings in S* of length up to bn+1. If we
find one, we say no, L(G) ¹ {e}. If we don’t find any, we can assert that L(G) = {e}. Why? If there is a
longer string in L(G) and we haven’t found it yet, then we know, by the pumping theorem, that we could
pump out vy from it until we got a string of length bn or less. If e were not in L(G), we could just test up to
length bn and if we didn’t find any elements of L(G) at all, we could stop, since if there were bigger ones
we could pump out and get shorter ones but there aren’t any. However, because e is in L(G), what about the
case where we pump out and get e? That’s why we go up to bn+1. If there are any long strings that pump
out to e, then there is a shortest such string, which can’t be longer than bn+1 since that’s the longest string
we can pump out.
c) {
L is not in D. If it were, then we could reduce GG= = {
to it and we have shown that GG= is not in D . Notice that L(G1) = L(G2) iff L(G1) Í L(G2) and L(G2) Í
L(G1). So, if we could solve the subset problem, then to find out whether L(G1) = L(G2), all we do is ask
whether the first language is a subset of the second and vice versa. If both answers are yes, we say yes.
Otherwise, we say no. Formally,we define R as follows:
R(
1. If M2(
If Oracle exists and decides L, then C = R(
•
•
But no machine to decide GG= can exist, so neither does Oracle.
23
23 Unrestricted Grammars
1) Write an unrestricted grammar for each of the following languages L:
a) { , n ≥ 0}.
S ® # ab %
# ® # D /* Each D is a doubler. Spawn (n-1) of them. Each of them will get pushed
to the right and will turn each a into aa and each b into bb as it passes over.
Da ® aaD /* Move right and double.
Db ® bbD ²
D% ® % /* D’s work is done. Wipe it out.
# ® e /* Get rid of the walls.
% ® e ²
G generates all strings in L: If no D’s are generated, G generates ab (n = 0). For any other value of n, the
correct number of D’s can be generated. G generates only strings in L: Once a D is generated, it cannot be
eliminated until it has made it all the way to the right and is next to %. To do that, it must double each a
and each b it passes over.
b) {anbmcn+m : n, m > 0}.
S ® a S c /* L is actually context free.
S ® a T c
T ® b T c
T ® b c
c) {anbmcnm : n, m > 0}.
S ® S1 # /* First generate Anbm#
S1 ® A S1
S1 ® A S2
S2 ® S2 b
S2 ® b
A ® a 1 /* For each A, in order to convert it to a, we will generate a 1.
/* Then we’ll push the 1 rightwards. As it passes over the b’s,
it will generate a C for each b. Start with the rightmost A or the
second 1 will get stuck.
1 a ® a 1
1 b ® b C 1
C b ® b C /* Move all the C’s to the right of the b’s.
C 1 # ® 1 # c /* Jump each C across # and convert it to c.
1 # ® # /* Get rid of 1 once all the C’s have jumped. If it goes too soon,
then some C’s will be stuck to the left of #.
b# c® bc /* Get rid of # at the end.
d) {anb2nc3n : n ³ 1}.
This one is very similar to anbncn. The only difference is that we will churn out b’s in pairs and c’s in
triples each time we expand S. So we get:
S ® aBSccc
S ® aBccc
n
a 2
n
b2
24
Ba ® aB
Bc ® bbc
Bb ® bbb
e) {wwRw : w Î {a, b}*}.
S ® S1 #
S1 ® a S1 a /* First generate wTwR#
S1 ® b S1 b
S1 ® T
/* Take each character of wR, starting at the left. Make a copy
of it and slide it to the right of the # to create the
second w. Use 1 for a and 2 for b.
T a ® T 1 A /* We’ll move A for a, B for b. And we’ll transform each character
T b ® T 2 B of wR as it is considered: a will be 1, b will be 2. These
two rules will handle the first such character.
1 a ® 1 1 A /* These next four will do this for characters 2 through n of wR.
1 b ® 1 2 B
2 a ® 2 1 A
2 b ® 2 2 B
A a ® a A /* Push A’s and B’s to the right until they hit #.
A b ® b A
B b ® b B
B a ® a B
A # ® # a /* Jump across #
B # ® # b
1 # ® # a /* Once all of wR has been converted to 1’s and 2’s (i.e., it’s all
2 # ® # b been copied), push # leftward converting 1’s back to a’s
and 2’s to b’s.
T # ® e /* Done.
f) {anbnanbn : n ³ 0}.
S ® % T
T ® A B T A B /* Generate n A’s and n B’s on each side of the middle marker #.
T ® # /* At this point, strings will look like: %ABABAB#ABABAB.
BA ® AB /* Move B’s to the right of A’s.
%A ® a /* Convert A’s to a’s and B’s to b’s, moving left to right.
aA ® aa ¢¢
aB ® ab
bB ® bb
#A ® a
% # ® e /* The special case where no A’s and B’s are generated.
g) {xy#xR : x, y Î {a, b}* and |x| = |y|}.
S ® a S X a /* Generate x#xR, with X’s mixed in. The X’s will become y.
S ® b S X b
S ® # /* At this point, we have something like aab#XbXaXa.
b X ® X b /* Push all the X’s to the left, up next to #.
a X ® X a /* At this point, we have something like aab#XXXbaa.
25
# X ® a # /* Hop each X leftward over # and convert it to a or b.
# X ® b #
2) Show that, if G, G1, and G2 are unrestricted grammars, then each of the following languages, defined in Section
23.4, is not in D:
a) Lb = {
We show that Ae ≤M Lb and so Lb is not decidable Let R be a mapping reduction from Ae = {
machine M accepts e}to Lb, defined as follows:
R(
1. From M, construct the description
2. Return
If Oracle exists and decides Lb, then C = Oracle(R(
machine using the algorithm presented in Section 23.2. And C is correct:
• If
• If
But no machine to decide Ae can exist, so neither does Oracle.
b) Lc = {
We show that EqTMs ≤M Lc and so Lc is not decidable Let R be a mapping reduction from EqTMs =
EqTMs = {
R(
1. From Ma, construct the description
2. From Mb, construct the description
3. Return
If Oracle exists and decides Lc, then C = Oracle(R(
as a Turing machine using the algorithm presented in Section 23.2. And C is correct:
• If
• If
But no machine to decide EqTMs can exist, so neither does Oracle.
c) Ld = {
The proof is by reduction from AANY = {
accepts}. Define:
R(
1. From M, construct the description
2. Return
{R, ¬} is a reduction from AANY to Ld. If Oracle exists and decides Ld, then C = ¬Oracle(R(
AANY. R can be implemented as a Turing machine using the algorithm presented in Section 23.2. And C is
correct:
26
• If
rejects. C accepts.
• If
Oracle(
But no machine to decide AANYe can exist, so neither does Oracle.
3) Show that, if G is an unrestricted grammar, then each of the following languages is not in D:
a) {
Let R be a mapping reduction from H to L defined as follows:
R(
1. Construct the description
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept.
2. Build the description
3. Return
If Oracle exists, then C = Oracle(R(
C is correct. G# generates S* or Æ, depending on whether M halts on w. So:
a. < M, w> Î H: M halts on w, so M# accepts all inputs. G# generates S*. a* Í S*. Oracle accepts.
• < M, w> Ï H: M does not halt on w, so M# halts on nothing. G# generates Æ. It is not true
that a* Í Æ. Oracle rejects.
But no machine to decide H can exist, so neither does Oracle.
b) {
4) Let G be the unrestricted grammar for the language AnBnCn = {anbncn : n ³ 0}, shown in Example 23.1.
Consider the proof, given in Section 36.4, of the undecidability of the Post Correspondence Problem. The proof
is by reduction from the membership problem for unrestricted grammars.
a) Define the MPCP instance MP that will be produced, given the input
defined in the proof of Theorem 36.1.
X Y
1 %S Þ %
2 & Þ abc%
3 S S
4 B B
5 a a
6 b b
7 c c
8 aBSc S
9 e S
10 aB Ba
11 bc Bc
12 bb Bb
13 Þ Þ
b) Find a solution for MP.
1, 8, 13, 5, 4, 9, 7, 13, 5, 11, 2.
27
c) Define the PCP instance P that will be built from MP by the reduction that is defined in the proof of
Theorem 36.2.
A B
0 ¢%¢S¢ Þ¢ ¢%
1 %¢S¢ Þ¢ ¢%
2 &¢ ¢Þ ¢a¢b¢c¢%
3 S¢ ¢S
4 B¢ ¢B
5 a¢ ¢a
6 b¢ ¢b
7 c¢ ¢c
8 a¢B¢S¢c¢ ¢S
9 e ¢S
10 a¢B¢ ¢B¢a
11 b¢c¢ ¢B¢c
12 b¢b¢ ¢B¢b
13 Þ¢ ¢Þ
14 $ ¢$
d) Find a solution for P.
0, 8, 13, 5, 4, 9, 7, 13, 5, 11, 2, 14.