GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
75 views
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?
asked in Theory of Computation by (119 points)   | 75 views
Undecidable. But It is recognizable (R.E)
it is neither decidable nor Recursively enurable
Right. If it were something like "L is a Regular Language and accepts regular sets", this would be a R.E, right? Because it can have a 'yes' ?

1 Answer

+2 votes
Best answer

$T_{yes}=\phi$

$T_{no}=0^{n}1^{n}$

using Rice theorem $2$,

Any non-monotonic property of the LANGUAGE recognizable by a Turing machine is unrecognizable 

non-monotonic property Holds as -:

$T_{yes}\subset T_{no}$

Hence is is not turing recognizable , so no chance of its decidablity.

answered by Veteran (10.9k points)  
selected by
can someone suggest a good video or liink to understand rice theorem easily please
What is recognizability? Can someone explain!

recognizablity?what recognizablity?

  • if a Language is turing recognizable,it will be accepted by Turing M/c,hence RE.

go through the link 

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

 

if we ask a question like "if a number is divisible by 2"

then there are two answer possible either "yes" or "no".

like take a number 8

if 8 is divisible by 2?

ans is yes

if we take a number 9, then answer will be "no"

So, where yes and no both ans possible, that language is called turing decidable language. Because we can definitely say yes and no ans for it

In turing recognizable language Similarly we can predict "yes" ans, but cannot say anything about "no" ans
Is there any other link, video or something for rice theorem and related stuff??

"Other than gatecse link."
(1) L(M)L(M) has at least 10 strings

We can have TyesTyes for Σ∗Σ∗ and TnoTno for ϕϕ. Hence, L={M∣L(M) has at least 10 strings}L={M∣L(M) has at least 10 strings} is not Turing decidable (not recursive). (Any other TyesTyes and TnoTno would also do. TyesTyes can be any TM which accepts at least 10 strings and TnoTno any TM which doesn’t accept at least 10 strings )

 

 

how this is not turing decidable

iunderstood the monotonic property ( part 2)

but not clear with PaRT 1

@sourav

@A_i_$_h

A language is decidable iff it is Recursive(i.e indirectly CSL,CFL,RL)

There is no point of arguing that a language which is not even RE will decidable or not !?

 

y its  is not RE ?
@sourav A language is decidable iff it is recursive -- not all r.e. languages are decidable.
@arjun sir, Thanks! I missed it.Updated!


Top Users Sep 2017
  1. Habibkhan

    7184 Points

  2. Warrior

    2664 Points

  3. Arjun

    2582 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1856 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,151 questions
33,733 answers
79,970 comments
31,120 users