For the remaining problems, assume that all of the machines mentioned in the que

Question

For the remaining problems, assume that all of the machines mentioned in the questions are over the alphabet 2a, b) Assume the strings representing machines mentioned in the questions are effective encodings over { a,b, #,0,1). 3. Explain what is wrong with the following "proof" for trying to show that the family of Recursively Enumerable languages are closed under complementation Suppose we are given a Recursively Enumerable language, L, over 2. Then there must be a Turing Machine (procedure) that recognizes L. Call the TM M". Since M is a TM, it can be represented as a string, w, over ',where w is a valid encoding of M. To produce a TM, M, that recognizes, L, construct M as follows. For any input string, x, over 2: M first writes the encoding, w, of M onto the work tape and copies its own input string, x, onto the work tape. Then M uses the Universal Turing Machine to simulate M on input string x. If the simulation of M on input x halts and accepts, then M rejects. If the simulation of M on input x halts ano rejects, then M accepts.

Explanation / Answer

In the above proof, we are forgetting a very important problem of the turing machine and the probem is:

Halting problem of Turing Machine

Halting problem of the turing machine is whether a turing machine will produce a 'yes' or 'no' in a finite number of steps.

Halting problem of the turing machine is undecidable.

In the given proof, we are saying if the simulation of M on input x halts and accept, then bar(M) rejects and if the simulation of M on input x halts and rejects, then bar(M) accepts. Since halting problem of Turing machine itself is undecidable, we can not use the given proof.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.