Introduction to the Theory of Computation

CSE 431, Spring 2011, University of Washington

Homework #3

Posted by James on April 14, 2011

Due: Wednesday, April 20th, in class.

Reading assignment: Sipser, Chapter 5.

In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that you are required to write up the solutions by yourself. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.

The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.

Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.

A final piece of advice: Start working on the problem sets early! Don’t wait until the day (or few days) before they’re due.


Each problem is worth 20 points unless otherwise noted.

  1. Decidable or undecidable?

    Which of the following problems about Turing machines is decidable and which is not? Briefly justify your answers.

    1. To determine, given a Turing machine M, whether M ever moves its head to the left when it is run on an input w.

    2. To determine, given a Turing machine M, whether it ever writes 0000 at any place on the tape, when run on the input 1111.

    3. To determine whether a Turing machine M ever modifies the input portion of the tape when run on input 1111.

    4. To determine, given a Turing machine M and an input w, whether M ever moves its tape head off the input portion of the tape.
  2. Separation.

    Let A and B be two disjoint languages. Say that C separates A and B if A \subseteq C and B \subseteq \overline{C}. Show that any two disjoint co-Turing-recognizable languages are separable by some decidable language.

  3. Mapping reducibility.

    1. Prove that a language A is Turing-recognizable if and only if A is mapping reducible to A_{\mathrm{TM}}.

    2. Prove that a language B is Turing-decidable if and only if B is mapping reducible to PALINDROMES.

  4. Unary!

    Show that there is an undecidable language L \subseteq \{1\}^*.


One Response to “Homework #3”

  1. Mary said

    Totally unrelated, but here’s a neat poem about the halting problem:

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: