Let STM-( | M is a Turing Machine and M accepts some string from ?*). a. Explain
ID: 3716425 • Letter: L
Question
Let STM-( | M is a Turing Machine and M accepts some string from ?*). a. Explain why the following "proof" that STM is Turing recognizable is incorrect. "Proof." Let (wi,wpW3, ) be the list of all strings in ?* in short lexicographic order (defined on p. 14 of the textbook). Then, the following Turing Machine R is a recognizer for S. On input : 1. Set i-1 Simulate the execution of M on wi. If M accepts, accept. Increment i and repeat step 2. 2. 3. b. Modify this incorrect "proof" to give a correct proof that STM is recognizable. (HINT: Consider the proof that a language is Turing recognizable if and only if some enumerator enumerates it.) Now, show that ETM = { 1 M is a Turing Machine and L(M) = Ø} is not Turing recognizable. c.Explanation / Answer
From the Definition of Recognizable wrt to Turing Machine - A language is Recognizable iff there is a Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects, or does not halt at all. Note: there is no requirement that the Turing Machine should halt for strings not in the language.
a) The proof is invalid because STM will accept some string over the set of input alphabets and will halt definitely. But we cannot say for which all strings the Turing Machine STM will reject because it is not mentioned for those set of strings the TM will never halt at all. Since we only the know the set of strings to be accepted for which the TM will halt and is unknown when the TM will reject the strings which are not a part of Language L, hence STM is recognizable is "wrong" in this context [Proved!]
b) Let STM = {<M> | M is a Turing Machine and M accepts all strings over ?* which starts with 0 and ends with 1}.
This is an example of Language which is Recognizable by TM since it will always accepts those strings in L that starts with 0 and ends with 1 and will Halt, and reject those strings that does not belong to L (i.e 000, 111, ....}
Hence we can say that STM is Turing Recognizable [Ans]
c) L(M) = { } [The Empty Set]. Now in this the empty set does not contain any strings that belong to L, because L is given as empty Set. So we cannot determine from this empty set those strings for which TM will accept and for other strings TM will reject as the set is empty. By this property we can say that L(M) is not Turing Recognizable as there are no strings to determine when the TM will halt and accept the strings which belong to L, and when the TM will reject the strings that are not in L (We cannot make this decision WHY? Because L is empty). So L(M) is not Turing Recognizable [Proved!]
Please let me know in case of any clarifications required. Thanks!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.