Computer Science 4602, Fall 2016
Assignment 5

Assigned: Thursday, October 20
Due: Tuesday, October 25 at the beginning of class

Exercises are from Sipser, third edition, beginning on page 187 for Chapter 3 and page 210 for Chapter 4.

  1. 3.15(d,e)
  2. 3.22
  3. Prove that every finite language is Turing-decidable (computable).
  4. Are all infinite languages uncomputable? Explain why or why not.
  5. 4.3
  6. 4.30
    (Hint: Write a program that takes integer inputs (so its input alphabet consists of decimal digits). On input i, it finds Mi and runs it on input i. What can your program do to ensure that your program does not compute the same language as Mi?