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

Homework 3 – Deadline June 19, 11:59 pm

June 8, 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.  [15 points] Suppose M is a single-tape TM with tape alphabet Γ and state space Q (where |Γ| = 10, |Q| = 10). On an input w of length n, suppose we are guaranteed that the TM on input w never goes beyond the first 2n cells. Define T = 1 + 100n  · 20n.  Prove that if the TM M on input w does not halt in the first T steps, then it will never halt on input w .

Hint:  Count the number of possible configurations.  Show that if the TM does not halt in T steps, there must be a repeated configuration.

2.  [15 points] Let L be a recursively enumerable language.  Define L\  = {x : 3 a prefix y of x such that y ∈ L}. Prove that L\  is recursively enumerable.

Note that a string y is said to be a prefix of x if there exists a string z such that yz = x.

3.   [15 points] Let L  ⊆ {0, 1}*  be a decidable language.  Let L0  be the lan- guage of palindromes over {0, 1}* . Prove that L ≤ L0 .