edited by
4,780 views

3 Answers

Best answer
15 votes
15 votes

You can apply Rice's Theorem . How ?

$L = \left \{ \left \langle M \right \rangle | TM\ halts\ on\ every\ input\ \right \} \Rightarrow L = \left \{\left \langle M \right \rangle | L(M)\ is\ Recursive \ \right \}$

Here, Implied Reduction exists. You pick a TM you know that halts on every Input and TM which halts on every input must have a Recursive (Decidable) Language.

So, this Language can be implied reduced to 

$L = \left \{\left \langle M \right \rangle | L(M)\ is\ Recursive \ \right \}$

  • Now, Simply apply Rice theorem 1 to prove it as Non Trivial-Property and hence, Undecidable.
  • Secondly, We can even apply Rice non monotonic Property (Rice second thorem) and see that Property of Language being Recursive is a Strict Subset of RE language, making this language not even Semi - Decidable.

For Rice theorem http://gatecse.in/rices-theorem/


Exercises :- 

1). $L = \left \{ \left \langle M \right \rangle | TM\ halts\ on\ No\ input\ \right \} \Rightarrow L = \left \{\left \langle M \right \rangle | L(M)\ is\ PHI \ \right \}$ ? 

(Again UD and Non RE ?)

2). $L = \left \{\left \langle M \right \rangle | L(M)\ is\ Regular \ \right \}$ ? 

3). $L = \left \{\left \langle M \right \rangle | L(M)\ is\ DCFL \ \right \}$ ? 

4). $L = \left \{\left \langle M \right \rangle | L(M)\ is\ CFL\ \right \}$ ? 

5). $L = \left \{\left \langle M \right \rangle | L(M)\ is\ CSL \ \right \}$ ? 

selected by
4 votes
4 votes

If TM halts on every input then it means TMs of those language which accepts everything in the Kleene's Closure which is not even semidecidable..The reason being the complement of this is :

TMs of languages which accept nothing i.e. the language is empty ..

which is an RE set as it is we know in reduction theory :

If X --> Y , and Y is known to be RE then X is also RE 

For our case , let X be the given problem of empty language and Y be the halting Turing machine problem which is partially decidable(RE but not REC)..

So X will also be RE following the reduction criteria..

And we know RE but not REC languages are not closed under complementation..

And in this case the dovetailing technique also fails as we never know that each of the infinite strings will be even accepted or not..

Hence the given description of Turing Machine is non recursively enumerable language.. 

Related questions

11 votes
11 votes
2 answers
1
sourav. asked Sep 9, 2017
4,381 views
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$I have to check that it is Turing Recogniza...
3 votes
3 votes
2 answers
2