Created: Mon Mar 17 2008
Last modified:
Assigned:
Thu Mar 20 2008
Due:
Thu Apr 03 2008
General Instructions
- Please review the
grading policy
outlined in the course information page.
- On the first page of each part of your solution write-up,
you must make explicit which problems are to be graded for
"regular credit", which problems are to be graded for "extra credit",
and which problems you did not attempt.
Please use a table something like the following
Problem | 01 | 02 | 03 | 04 |
05 | 06 | 07 | 08 | 09 | ... |
Credit | RC | RC | RC | EC | RC |
RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA"
is "not applicable" (not attempted). Failure to do so will result
in an arbitrary set of problems being graded for regular
credit, no problems being graded for extra credit, and a five percent
penalty assessment.
- You must also write down with whom you worked on the assignment. If this
changes from problem to problem, then you should write down this
information separately with each problem.
Specific Instructions
Note: It is quite possible to solve the questions on this
assignment in many correct ways. In particular, one can reduce
from many undecidable problems to show that any of the
languages given below are undecidable; however, choosing the "wrong"
reduction will result in a complicated solution.
In the hints that follow, I will describe particularly simple
reductions that result in simle solutions. Your solutions need
not follow these hints; many correct solutions reducing from
different languages exist.
Each hint below corresponds to a matching problem (Hint 1 for Problem
1; Hint 2 for Problem 2, etc.)
- Reduce from ATM. Your
reduction will be similar to the reduction we used to show that
REGTM was undecidable:
M' will filter its inputs and take one action if the
input string is "000" and another if the input string is not.
- Again, reduce from ATM. Note
that |L(M)| >= 2 means that the size of the language accepted
by M must be at least two; i.e., M accepts at
least two strings. In your reduction, have M' always
accept one string (pick your favorite), and let it accept a second
(or more)strings if and only if M accepts w.
- Reduce from ATM. Your
reduction will be similar to the reduction we used to show that
REGTM was undecidable:
M' will filter its inputs and take one action if the
input string is of the form
0*1* and
another if the input string is not. You may need to "flip" the
output bit...
- Reduce from EINTTM. Think
about how you should set k and whether you should flip
the output bit or not. This is perhaps the easiest problem on this
assignment.
- Again, reduce from ATM.
M' should accept some particular string which is
not its own reverse (pick your favorite), and it should
accept all other strings if and only if M accepts
w. Think about the consequences of such a reduction.
- This problem is not a reduction in our usual sense. What you need
to think about is this: How could you solve
ETM using a subroutine which
minimizes Turing Machines? If you could do that, then such a
subroutine can't exist... So, you have to build a program which
solves ETM from the subroutine
which minimizes TMs. ETM
questions are of the form, "Here's a TM, does it accept the empty
language, i.e., no strings?" Suppose I give you a TM which
accepts no stings, and you minimize it; what will it look like?
Suppose I give you a TM which accepts some strings and you
minimize it; what will it look like? Can you tell the difference?
If so, you can solve ETM using
the subroutine in question...
Describe carefully how you would solve
ETM using the subroutine in
question, and that in and of itself will demonstrate that the
subroutine cannot exist.
Problems
Required: 4 of the following 6 problems
Points: 25 pts per problem
- Prove that the following language is undecidable.
L = {<M> | M is a Turing machine, and M accepts the string "000"}
- Prove that the following language is undecidable.
L = {<M> | M is a Turing machine and |L(M)| >= 2}
- Prove that the following language is undecidable.
L = {<M> | M is a Turing machine, and L(M) =
0*1*}
- Prove that the following language is undecidable.
L =
{<M1,M2,k>
| M1 and M2 are
Turing machines, and |L(M1) int
L(M2)| >= k}
Here "int" is set intersection.
- Exercise 5.9
- As we have mentioned in class, an algorithm for minimizing finite automata
exists: Given as input a DFA D, the algorithm returns a DFA
D' where L(D) = L(D') and D' contains
as few states as possible.
Show that no such procedure for minimizing Turing Machines can exist; i.e.,
show that a procedure which takes as input a Turing Machine and returns
as output the minimum equivalent Turing Machine cannot exist.
Hint: We have shown that ETM
is undecidable. What is the smallest TM which accepts the empty language?
Could you recognize such a TM if it were handed to you? Show how you could
solve ETM if you had a procedure for
minimizing TMs; thus, such a procedure cannot exist.
Note: This result essentially implies that one cannot write
a procedure which takes as input a program and returns as output the
smallest equivalent program. Such a procedure could be extremely useful,
if it existed; think about the ramifications of such a procedure for the
software industry.
Switch to:
fell@ccs.neu.edu