Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework 3 – Deadline June 24, 11:59 pm

June 14, 2023

Instructions:  The goal of this course is to strive for mathematical clarity in computation. In that spirit, please make sure your answers are clear, concise and rigorous.  The onus for all three is on you.  Use a word processor to type your answers (preferably Latex).

You will be allowed to collaborate in groups of two.  But you must write your solutions individually.

1.  [10 points] Let L = {⟨M⟩,x,y : M accepts exactly one of x or y} . Prove that L is not recursively enumerable by reducing from ATM .

2.   [10 points] Prove that L ≤  ATM   if and only if L is recursively enumer- able.

3.   [10 points] Let P be a property of languages and let M0  be a TM such that L(M0 ) ∈  P .  Further, assume that any finite subset of L(M0 ) does not have property P (in particular, the language L(M0 ) is an infinite set).

Prove that LP    =  {⟨M⟩  :  L(M)  ∈  P}  is not recursively enumerable by reducing from ATM .