GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
72 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)   | 72 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.6k 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

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2052 Points

  5. A_i_$_h

    1990 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,037 questions
33,645 answers
79,693 comments
31,069 users