Computer Science 6420
Spring 2006
Practice Questions for Exam 1

1. Let S be a set of strings. What does it mean for S to be computable?

2. Let S be a set of strings. What does it mean for S to be partially computable?

3. What is the definition of an m-reduction between two sets?

4. What is the definition of an m-complete set?

5. A configuration of pieces on an 8x8 chessboard can be described by a string. The configuration tells which piece (if any) is in each square, and whose move is next. Consider the set W of all chessboard configurations where black has a winning strategy. Is W a computable set of strings?

6. Consider the set B = {p | phi_p(0) = phi_p(1)}. Set B contains all programs that produce the same result on input 1 as on input 0. Is B computable? Why or why not?

7. Is the set {(p,q) | p and q are not equivalent programs} computable? Prove your result.

8. Let A = {p | phi_p(1) = 1} and B = {p | phi_p(1) = 2}. Show that A m-reduces to B.

9. Show that the set A from the preceding question is partially computable.

10. Show that the set A from the preceding question is m-complete.

11. Give an example of a set that is not partially computable. How do you know that it is not partially computable?

12. Post's correspondence problem involves a collection of dominoes, where each domino has a top and bottom part. The two parts are connected together, and you have to keep them together. What if you separated the top and bottom? Here is a variation on Post's correspondence problem.

    Input. Two collections of strings, t₁, t₂, ..., t_n and b₁, b₂, ..., b_n, representing the tops and bottoms of dominoes.

    Question. Does there exist a sequence of (at least one of) the top dominoes and a sequence of (at least one of) the bottom dominoes that, when put together, make exactly the same string? For this problem, you are not required to select the tops and bottoms in the same way. For example, you would say yes it if turns out that t₂t₅ = b₃b₁b₉.

    Is this problem computable? If so, describe an algorithm to solve it. If not, why not? (Hint. You can build a finite state machine that recognized exactly the strings that can be obtained by concatenating some collection of a given finite set of strings together. Also, given two finite state machines M₁ and M₂, you can create another finite state machine that accepts exactly the strings that are accepted by both M₁ and M₂.)