HW6CSE105F24: Homework assignment 6

In this assignment,

You will practice analyzing, designing, and working with Turing machines. You will use general constructions and specific machines to explore the classes of recognizable and decidable languages. You will explore various ways to encode machines as strings so that computational problems can be recognized.

Resources: To review the topics for this assignment, see the class material from Weeks 8 and 9. We will post frequently asked questions and our answers to them in a pinned Piazza post.

Reading and extra practice problems: Sipser Sections 4.2, 5.3, 5.1. Chapter 4 exercises 4.9, 4.12. Chapter 5 exercises 5.4, 5.5, 5.6, 5.7. Chapter 5 problems 5.22, 5.23, 5.24, 5.28

For all HW assignments: Weekly homework may be done individually or in groups of up to 3 students. You may switch HW partners for different HW assignments. Please ensure your name(s) and PID(s) are clearly visible on the first page of your homework submission and then upload the PDF to Gradescope. If working in a group, submit only one submission per group: one partner uploads the submission through their Gradescope account and then adds the other group member(s) to the Gradescope submission by selecting their name(s) in the “Add Group Members" dialog box. You will need to re-add your group member(s) every time you resubmit a new version of your assignment. Each homework question will be graded either for correctness (including clear and precise explanations and justifications of all answers) or fair effort completeness. For “graded for correctness” questions: collaboration is allowed only with CSE 105 students in your group; if your group has questions about a problem, you may ask in drop-in help hours or post a private post (visible only to the Instructors) on Piazza. For “graded for completeness” questions: collaboration is allowed with any CSE 105 students this quarter; if your group has questions about a problem, you may ask in drop-in help hours or post a public post on Piazza.

All submitted homework for this class must be typed. You can use a word processing editor if you like (Microsoft Word, Open Office, Notepad, Vim, Google Docs, etc.) but you might find it useful to take this opportunity to learn LaTeX. LaTeX is a markup language used widely in computer science and mathematics. The homework assignments are typed using LaTeX and you can use the source files as templates for typesetting your solutions. To generate state diagrams of machines,you can (1) use the LaTex tikzpicture environment (see templates in the class notes), or (2)) use the software tools Flap.js or JFLAP described in the class syllabus (and include a screenshot in your PDF), or (3) you can carefully and clearly hand-draw the diagram and take a picture and include it in your PDF. We recommend that you submit early drafts to Gradescope so that in case of any technical difficulties, at least some of your work is present. You may update your submission as many times as you’d like up to the deadline.

Integrity reminders

• Problems should be solved together, not divided up between the partners. The homework is designed to give you practice with the main concepts and techniques of the course, while getting to know and learn from your classmates.

• You may not collaborate on homework questions graded for correctness with anyone other than your group members. You may ask questions about the homework in office hours (of the instructor, TAs, and/or tutors) and on Piazza (as private notes viewable only to the Instructors). You cannot use any online resources about the course content other than the class material from this quarter – this is primarily to ensure that we all use consistent notation and definitions (aligned with the textbook) and also to protect the learning experience you will have when the ‘aha’ moments of solving the problem authentically happen.

• Do not share written solutions or partial solutions for homework with other students in the class who are not in your group. Doing so would dilute their learning experience and detract from their success in the class.

You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called “hw6CSE105F24”.

Assigned questions

1. What’s wrong with these reductions? (if anything) (15 points): Suppose your friends are practicing coming up with mapping reductions \(A \leq_m B\) and their witnessing functions \(f: \Sigma^* \to \Sigma^*\). For each of the following attempts, determine if it has error(s) or is correct. Do so by labelling each attempt with all and only the labels below that apply, and justifying this labelling.

   • Error Type 1: The given function can’t witness the claimed mapping reduction because there exists an \(x \in A\) such that \(f(x) \not\in B\).

   • Error Type 2: The given function can’t witness the claimed mapping reduction because there exists an \(x \not\in A\) such that \(f(x) \in B\).

   • Error Type 3: The given function can’t witness the claimed mapping reduction because the specified function is not computable.

   • Correct: The claimed mapping reduction is true and is witnessed by the given function.

   Clearly present your answer by providing a brief (3-4 sentences or so) justification for whether each of these labels applies to each example.

   1. (Graded for completeness) ¹ \(A_{\mathrm{TM}} \le_m HALT_{\mathrm{TM}}\) and \[f(x) = \begin{cases} \scalebox{.7}{$\langle$ \hspace{-.5cm} \raisebox{-.4cm}{ \begin{tikzpicture}[->,>=stealth',shorten >=1pt, auto, node distance=2cm, semithick] \tikzstyle{every state}=[text=black, fill=none] \node[initial,state,accepting] (q0) {$q_{\mathrm{acc}}$}; ; \end{tikzpicture}} $, \varepsilon \rangle$} & \text{if } x = \langle M, w \rangle \text{ for a Turing machine $M$ and string $w$}\\ & \qquad \qquad \text{ and } w \in L(M) \\ \scalebox{.7}{$\langle$ \hspace{-.5cm} \raisebox{-.4cm}{ \begin{tikzpicture}[->,>=stealth',shorten >=1pt, auto, node distance=2cm, semithick] \tikzstyle{every state}=[text=black, fill=none] \node[initial,state] (q0) {$q_0$}; \node[state,accepting] (qacc) [right of = q0, xshift = 20]{$q_{acc}$}; \path (q0) edge [loop above] node {$0, 1, \scalebox{1.5}{\textvisiblespace}\to R$} (q0) ; \end{tikzpicture}} $\rangle$} & \text{otherwise} \end{cases}\]

   2. (Graded for completeness) \(A_{\mathrm{TM}} \le_m EQ_{\mathrm{TM}}\) with \[f(x) = \begin{cases} \scalebox{.7}{$\langle$ \hspace{-.5cm} \raisebox{-.4cm}{ \begin{tikzpicture}[->,>=stealth',shorten >=1pt, auto, node distance=2cm, semithick] \tikzstyle{every state}=[text=black, fill=none] \node[initial,state,accepting] (q0) {$q_{\mathrm{acc}}$}; ; \end{tikzpicture}} , $M_w \rangle$} & \text{if } x = \langle M, w \rangle \text{ for a Turing machine $M$ and string $w$}\\\\ \scalebox{.7}{$\langle$ \hspace{-.5cm} \raisebox{-.4cm}{ \begin{tikzpicture}[->,>=stealth',shorten >=1pt, auto, node distance=2cm, semithick] \tikzstyle{every state}=[text=black, fill=none] \node[initial,state,accepting] (q0) {$q_{\mathrm{acc}}$}; ; \end{tikzpicture}}} , ~~~ \scalebox{.7}{\hspace{-.5cm} \raisebox{-.4cm}{\begin{tikzpicture}[->,>=stealth',shorten >=1pt, auto, node distance=2cm, semithick] \tikzstyle{every state}=[text=black, fill=none] \node[initial,state] (qrej) {$q_{\mathrm{rej}}$}; \node[state,accepting] (qacc) [right of=qrej] {$q_{\mathrm{acc}}$}; ; \end{tikzpicture}}$\rangle$ } & \text{otherwise}. \end{cases}\] Where for each Turing machine \(M\), we define \[\begin{aligned} M_w = ``&\text{On input } y \\ &1. \text{ Simulate $M$ on $w$.}\\ &2. \text{ If it accepts, accept.}\\ &3. \text{ If it rejects, reject."} \end{aligned}\]

   3. (Graded for correctness) ² \(HALT_{\mathrm{TM}} \le_m EQ_{\mathrm{TM}}\) with \[f(x) = \begin{cases} \scalebox{.7}{$\langle$ \hspace{-.5cm} \raisebox{-.4cm}{ \begin{tikzpicture}[->,>=stealth',shorten >=1pt, auto, node distance=2cm, semithick] \tikzstyle{every state}=[text=black, fill=none] \node[initial,state,accepting] (q0) {$q_{\mathrm{acc}}$}; ; \end{tikzpicture}} , $M_w \rangle$} & \text{if } x = \langle M, w \rangle \text{ for a Turing machine $M$ and string $w$}\\\\ \scalebox{.7}{$\langle$ \hspace{-.5cm} \raisebox{-.4cm}{ \begin{tikzpicture}[->,>=stealth',shorten >=1pt, auto, node distance=2cm, semithick] \tikzstyle{every state}=[text=black, fill=none] \node[initial,state,accepting] (q0) {$q_{\mathrm{acc}}$}; ; \end{tikzpicture}}} , ~~~ \scalebox{.7}{\hspace{-.5cm} \raisebox{-.4cm}{\begin{tikzpicture}[->,>=stealth',shorten >=1pt, auto, node distance=2cm, semithick] \tikzstyle{every state}=[text=black, fill=none] \node[initial,state] (qrej) {$q_{\mathrm{rej}}$}; \node[state,accepting] (qacc) [right of=qrej] {$q_{\mathrm{acc}}$}; ; \end{tikzpicture}}$\rangle$ } & \text{otherwise}. \end{cases}\] Where for each Turing machine \(M\), we define \[\begin{aligned} M_w = ``&\text{On input } y \\ &1. \text{ If } y \text{ is not the empty string, reject.}\\ &2. \text{ Else, simulate $M$ on $w$.}\\ &3. \text{ If it accepts, accept.}\\ &4. \text{ If it rejects, reject."} \end{aligned}\]

   4. (Graded for correctness) \(\{w w \mid w \in \{0,1\}^* \} \leq \emptyset\) and \(f(x) = 1\) for each \(x \in \{0,1\}^*\).

   5. (Graded for correctness) \(\emptyset \le_m \{w w \mid w \in \{0,1\}^* \}\) and \(f(x) = 1\) for each \(x \in \{0,1\}^*\).

2. Using mapping reductions (14 points): Consider the following computational problems we’ve discussed \[\begin{aligned} A_{TM} &= \{ \langle M, w \rangle \mid M \text{ is a Turing machine, } w \text{ is a string and $M$ accepts $w$}\} \\ HALT_{TM} &= \{ \langle M, w \rangle \mid M \text{ is a Turing machine, } w \text{ is a string and $M$ halts on $w$}\} \\ E_{TM} &= \{ \langle M \rangle \mid M \text{ is a Turing machine and } L(M) = \emptyset\} \\ EQ_{TM} &= \{ \langle M_1, M_2 \rangle \mid M_1, M_2 \text{ are both Turing machines and } L(M_1) = L(M_2) \} \end{aligned}\] and the new computational problem \[Two_{TM} = \{ \langle M \rangle \mid M \text{ is a Turing machine and $M$ accepts exactly one string} \}\] NOTE: the intended definition of \(Two_{TM}\) is that \(M\) accepts exactly two strings.

   1. (Graded for correctness) Give an example of a string that is an element of \(Two_{TM}\) and a string that is not an element of \(Two_{TM}\) and briefly justify your choices.

   2. (Graded for completeness) Prove that \(Two_{TM}\) is not decidable by showing that \(A_{TM} \leq_m Two_{TM}\).

   3. (Graded for correctness) Give a different proof that \(Two_{TM}\) is not decidable by showing that \(HALT_{TM} \leq_m Two_{TM}\).

   4. (Graded for completeness) Is \(Two_{TM}\) recognizable? Justify your answer.

3. Using mapping reductions (14 points): Consider the following computational problems we’ve discussed \[\begin{aligned} A_{TM} &= \{ \langle M, w \rangle \mid M \text{ is a Turing machine, } w \text{ is a string and $M$ accepts $w$}\} \\ HALT_{TM} &= \{ \langle M, w \rangle \mid M \text{ is a Turing machine, } w \text{ is a string and $M$ halts on $w$}\} \\ E_{TM} &= \{ \langle M \rangle \mid M \text{ is a Turing machine and } L(M) = \emptyset\} \\ EQ_{TM} &= \{ \langle M_1, M_2 \rangle \mid M_1, M_2 \text{ are both Turing machines and } L(M_1) = L(M_2) \} \end{aligned}\] and the new computational problem \[\begin{aligned} Evens_{TM} &= \{ \langle M \rangle \mid M \text{ is a Turing machine and any string that $M$ accepts must be even length}\\ &\text{(but there may even length strings that $M$ doesn't accept)} \} \end{aligned}\]

   1. (Graded for correctness) Give an example of a string that is an element of \(Evens_{TM}\) and a string that is not an element of \(Evens_{TM}\) and briefly justify your choices.

   2. (Graded for completeness) Prove that \(Evens_{TM}\) is not decidable by showing that \(\overline{HALT_{TM}} \leq_m Evens_{TM}\). This was changed Nov 26.

   3. (Graded for correctness) Give a different proof that \(Evens_{TM}\) is not decidable by showing that \(\overline{A_{TM}} \leq_m Evens_{TM}\). This was changed Nov 26.

   4. (Graded for completeness) Is \(Evens_{TM}\) recognizable? Justify your answer.

4. Examples of languages (7 points):

   For each part of the question, use precise mathematical notation or English to define your examples and then briefly justify why they work.

   1. (Graded for correctness) Two undecidable languages \(L_1\) and \(L_2\) over the same alphabet whose intersection \(L_1 \cap L_2\) is decidable, or write NONE if there is no such example (and explain why).

   2. (Graded for correctness) A regular language \(L_3\) and an unrecognizable language \(L_4\) over the same alphabet whose set-wise concatenation \(L_3 \circ L_4\) is unrecognizable, or write NONE if there is no such example (and explain why).

   3. (Graded for completeness) A co-recognizable language \(L_5\) that is NP-complete, or write NONE if there is no such example (and explain why). Recall the definition: A language \(L\) over an alphabet \(\Sigma\) is called co-recognizable if its complement, defined as \(\Sigma^* \setminus L = \{ x \in \Sigma^* \mid x \notin L \}\), is Turing-recognizable.