CSE105Sp HW5: Recognizability, Decidability, Undecidability, and
homework | 代写Turing machines | 编译原理代写 | automaton代写 | 自动机代写 | Compilation principle |
computational theory | 计算理论代写 | assignment代做 – 这是一个自动机的practice, 考察Turing machines的理解, 涵盖了automaton等方面, 该题目是值得借鉴的计算理论代写的题目
Reductions
CSE105Sp
Gradescope
In this assignment,
You will practice designing and working with Turing machines and their variants. You will use general constructions and specific machines to explore the classes of recognizable, decidable, and undecidable languages. You will use computable functions to relate the difficult levels of languages via mapping reduction.
Resources: To review the topics you are working with for this assignment, see the class material from Weeks 6, 7, 8. We will post frequently asked questions and our answers to them in a pinned Piazza post.
Reading and extra practice problems: Chapter 4 exercises 4.1, 4.3, 4.4., 4.5. Chapter 4 Problems 4.29, 4.30, 4.32. Chapter 5 exercises 5.4, 5.5, 5.6, 5.7. Chapter 5 problems 5.10, 5.11, 5.16, 5.18.
Key Concepts: Formal definitions of Turing machines, computations of Turing machines, halt- ing computations, implementation-level descriptions of Turing machines, high-level descriptions of Turing machines, recognizable languages, decidable languages, variants of Turing machines, enumerators, nondeterministic Turing machines, Church-Turing thesis, computational problems, diagonalization, undecidability, unrecognizability, computable function, mapping reduction.
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. The lowest HW score will not be included in your overall HW average. 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. You may only collaborate on HW with CSE 105 students in your group; if your group has questions about a HW problem, you may ask in drop-in help hours or post a private post (visible only to the Instructors) 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 opport unity 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, we recommend using Flap.js or JFLAP. Photographs of clearly hand-drawn diagrams may also be used. 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 youd 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 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 we will use this quarter 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 assign- ment called HW5CSE105Sp22.
Assigned questions
- (Graded for correctness^1 )
(a) Give an example of a decidable languageL 1 whose complement is also decidable. A
complete solution will include either (1) a precise definition of the example language
L 1 and an explanation of why it is decidable and why its complement is decidable, or
(2) a sufficiently general and correct argument for why there is no way to choose an
example language to satisfy this requirement. All justifications and arguments should
connect to the relevant definitions and the specific concepts being discussed.
(b) Give an example of a decidable languageL 2 and a Turing machineM 2 such that
L(M 2 ) =L 2 butM 2 does not decideL 2. A complete solution will include either (1)
precise definitions ofL 2 andM 2 and justifications for whyL(M 2 ) =L 2 and whyM 2
does not decideL 2 , or (2) a sufficiently general and correct argument for why there
is no way to choose such a language and machine. For any machines you discuss, you
can choose whether to use high-level descriptions, implementation level descriptions,
or formal definitions. All justifications and arguments should connect to the relevant
definitions and the specific concepts being discussed.
- (Graded for fair effort completeness^2 ) Recall that a set Xis said to beclosedunder an operationOP if, for any elements in X, applyingOPto them gives an element inX. For example, the set of integers is closed under multiplication because if we take any two integers, their product is also an integer. SupposeM 1 andM 2 are Turing machines. Consider the following high-level descriptions of machines that give general constructions based onM 1 andM 2.
(a) Consider the following construction of a nondeterministic Turing machine:
On inputw
- Nondeterministically splitw into two pieces, i.e. choosex, ysuch that w=xy.
- Simulate runningM 1 onx.
- Simulate runningM 2 ony.
- If both simulations in steps 2 and 3 accept, accept.
(^1) This means your solution will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound. (^2) This means you will get full credit so long as your submission demonstrates honest effort to answer the question. You will not be penalized for incorrect answers. To demonstrate your honest effort in answering the question, we ask that you include your attempt to answer each part of the question. If you get stuck with your attempt, you can still demonstrate your effort by explaining where you got stuck and what you did to try to get unstuck.
Can this construction be used to prove that the class of Turing-recognizable languages
is closed under concatenation? Briefly justify your answer.
(b) Consider the following construction of an enumerator:
Without any input
- Build an enumeratorE 1 that is equivalent toM 1.
- Build an enumeratorE 2 that is equivalent toM 2.
- StartE 1 running and startE 2 running.
- Initialize a list of all strings that have been printed byE 1. Declare the variablen 1 to be the length of this list (initiallyn 1 = 0).
- Initialize a list of all strings that have been printed byE 2 so far. Declare the variablen 2 to be the length of this list (initiallyn 2 = 0).
- Every time a new stringxis printed byE 1 :
- Add this string to the list of strings printed byE 1 so far.
- Incrementn 1 so it stores the current length of the list.
- Forj= 1… n 2 ,
- Letwjbe thejth string in the list of strings printed byE 2
- Printxwj.
- Every time a new stringyis printed byE 2 :
- Add this string to the list of strings printed byE 2 so far.
- Incrementn 2 so it stores the current length of the list.
- Fori= 1… n 1 ,
- Letuibe theith string in the list of strings printed byE 1
- Printuiy. Can this construction be used to prove that the class of Turing-recognizable languages is closed under concatenation? Briefly justify your answer. (c) Consider the following construction of a Turing machine: On inputw
- Letn=|w|.
- Create a two dimensional array of stringssm,j where 0 m nand 0 j1.
- For each 0mn, initializesm, 0 to be the prefix ofwof lengthmand sm, 1 to be the suffix ofwof lengthnm. In other words,w=sm, 0 sm, 1 and|sm, 0 |=m,|sm, 1 |=nm.
- Fori= 1, 2 ,…
- Fork= 0,… , i
- RunM 1 onsmin (k,n), 0 for (at most)isteps.
- RunM 2 onsmin (k,n), 1 for (at most)isteps.
- If both simulations in steps 6 and 7 accept, accept.
Can this construction be used to prove that the class of Turing-recognizable languages
is closed under concatenation? Briefly justify your answer.
- (Graded for fair effort completeness) Recall that
AT M={M, w|Mis a Turing machine,wis a string, andwL(M)}
and
HALTT M={M, w|Mis a Turing machine,wis a string, andM halts onw}
Consider the Turing machines below, with input alphabet = { 0 , 1 }, tape alphabet
{ 0 , 1 , }, and state diagrams (with the usual conventions):
(a) Give an example string that is in bothAT MandHALTT M and that is related to one
of the two Turing machines whose state diagrams are given above, or explain why
there is no such string.
(b) Give an example string that is inAT Mand is not inHALTT Mand that is related to
one of the two Turing machines whose state diagrams are given above, or explain why
there is no such string.
(c) Give an example string that is not inAT Mand is inHALTT Mand that is related to
one of the two Turing machines whose state diagrams are given above, or explain why
there is no such string.
- (Graded for correctness) Fix ={ 0 , 1 }for this question. For each part below, you can choose sets from the following list:
, AT M,AT M, HALTT M,HALTT M, ET M,ET M, EQT M,EQT M,
You may use each set from the listat most oncein the examples below. In particular,
you cant chooseA=B=C=D=X=Y = .
(a) Find setsA, Bfor which the computable function
F= On inputx
- Output , 00 .
witnesses the mapping reductionAm B. Justify your answer by proving that, for
all stringsx,xAiffF(x)B. If no such sets exist, justify why not.
(b) Find setsC, Dfor which the computable function
G= On inputx
- Check ifx=M, wforMa Turing machine andwa string. If so, go to step 3.
- If not, output , .
- Construct the Turing machineMx= On inputy,
- Ifyhas a positive and odd length, reject.
- Else, ifyhas a positive and even length, accept.
- Otherwise, runM onwand, if the computation halts, accepty.
- OutputMx, . witnesses the mapping reductionCmD. Justify your answer by proving that, for all stringsx,xC iffG(x)D. If no such sets exist, justify why not.
(c) Find setsX, Y for which the computable function
H= On inputx
- Check ifx=M, wforM a Turing machine andwa string. If so, go to step 3.
- If not, output .
- Construct the Turing machineMx = On inputy,
- Ify 6 =w, reject.
- Otherwise, runMonw.
- IfM accepts, accept. IfMrejects, reject.
- OutputMx. witnesses a mapping reductionXmY. Justify your answer by proving that, for all stringsx,xXiffH(x)Y. If no such sets exist, justify why not.