CIS2620 Summer 2023 Assignment 4
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 .
2023-06-27