Due. Wednesday, Feb. 23 at the beginning of class.
Write clearly readable and well thought out answers to all of the following questions.
What is the definition of an m-reduction between two languages?
What is the definition of an m-complete language?
Is it possible for an m-complete language to be computable?
Define A = {p | program p halts on all strings in {a,b}* that have length less than 4}. Show that A is m-complete.
Let U be the language {(M,x) | M(x) does not halt}. Is U m-complete? Explain.
Let L be the language {(M, x, q) | M is (a description of) a Turing machine with input alphabet {a,b}, x is a string in {a,b}*, and q is a state in M, where state q is reached at some point while running M on input x}. Is L is a computable language? Prove your answer.