CSCI 6420
Spring 2014
Homework Assignment 2
Due: Friday, February 7

  1. Read exercise 5.28 and its solution (pages 213 and 215) in Sipser. Also read an alternative explanation of Rice's theorem below. Solve problem 5.30 (a,b,c), page 213. Notation L(M) indicates the set of all strings that M accepts. Σ* indicates the set of all strings over the input alphabet of M.

  2. Solve problem 5.31, page 213, of Sipser. But instead of assuming that ATM is computable, assume that the following set is computable. 

      {p | p is a program that stops on every input}
    Show how to use a program that solves that set to get an answer to the 3x+1 problem. You do not need to work directly with Turing machines. Assume that you can express programs in any reasonable way.

 

Definition. Let S be a set of strings over alphabet A. The complement S of S is the set of all strings over alphabet A that are not in S.

Definition. A set of strings S over alphabet A is nontrivial if neither S nor S is an empty set.

Definition. Two programs p and q are equivalent if

  1. for every string x, p(x) halts if and only if q(x) halts;
  2. for every string x, if p(x) halts then p(x) and q(x) give the same answer.

Definition. Let S be a set of programs. Say that S respects equivalence if, whenever p and q are two equivalence programs, either p and q are both in S or p and q are both not in S.

Recall that a set of strings S is computable if the membership problem for S is computable. The membership problem of S is the problem given as follows.

Input: string x.
Question. Is x in S?

Rice's Theorem. If S is a nontrivial set of programs that respects equivalence then S is uncomputable.