CS 456/656 Study Problems 2

Due date: November 3, 2005, 4:00 PM.

This assignment should be worked, but not handed in, since an examination is scheduled for that day.
  1. Work Exercise 3.1 on page 159 of your textbook.
  2. Work Exercise 3.2 on page 159 of your textbook.
  3. Design a Turing Machine whose tape alphabet is {0,1} which right-shifts any string over {0,1}. Specifically, if the initial configuration of the machine is q0w, where w is a string over {0,1}, then the final configuration of the machine is #hacceptw, where # represents a blank. Your machine must not use any tape symbols other than 0,1, and blank.
  4. Explain informally, using pictures and words, how any 2-tape Turing Machine can be emulated by a Turing Machine.
  5. Is it true that every language that is decided by some machine is accepted by some machine?
    Is it true that every language that is accepted by some machine is decided by some machine?
  6. Let L be a language. What is an enumerator of L? You may use either the definition given in class, the one on page 152 of your textbook, or another one that you found in a different textbook.
    You learned in your math class that every countable set is enumerable. (In fact, "countable" is a synonym for "enumerable.") Every language is countable. Yet, you have learned in 456/656 that some languages do not have enumerators.
    Explain this apparent contradiction.
  7. Explain informally how any language L that is accepted by an NTM (non-deterministic Turing machine) is accepted by some TM. Remember: by definition, a TM is deterministic.
  8. This one is a bit tricky. I have a proof that every language is decidable. What is wrong with that proof?

Back to Course Page