Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CompSci 162 Formal Languages and Automata Problem Set 4: Decidability
Formatting: please start each numbered question on a separate piece of paper, and limit your response to one page. Upload a PDF consisting of these three pages to GradeScope and tag each page. Write in dark ink on light paper, whether you are producing your work digitally or on physical paper. I realize this seems strict, but it really does help with grading, especially with a large class.
Please review the syllabus and course reference for the expectations of assignments in this class. Remember that problem sets are not online treasure hunts. Remember that you may not seek help from any source where not all respondents are subject to UC Irvine’s academic honesty policy.
Please also remember you have a professor and four TAs who want to help you. If you’re lost on this, let us know!
1. Let Σ = {1}. Construct a deterministic Turing Machine that computes the function f : Σ∗ → Σ ∗ such that f(⟨n⟩) = ⟨3n⟩ for all n ∈ N, where ⟨k⟩ means the encoding of the natural number k as a unary number; that is, the number k is encoded as the string 1k .
(a) Carefully describe the idea behind your machine
(b) Draw a complete state diagram of the machine
2. Consider the language L2 : {⟨M, w⟩ : M never moves its head past the initial input string when w is the input.} Note that this is similar to something in lecture, but is not exactly the same problem. Prove that L2 is decidable.
3. Consider the following language L3 : {⟨M, w⟩ : M eventually writes a blank somewhere on its tape, given input string w}.
Show that L is undecidable. You may use the fact that the halting language is undecidable in your proof (and you are encouraged to do so).