The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
131 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 (139 points) | 131 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 (15.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!


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,101 questions
36,904 answers
91,826 comments
34,770 users