search
Log In
2 votes
237 views

I was Studying About Undecidability on GateCSE. I am facing a doubt that :

  1. L = {<M> | M accepts "1"}
     L is set of String & each String is an Encoding of TM & TM accepts 1
  2. L = {<M> | L(M) = {1}}
    Given a Input Program we have to see it  Accepts 1 & nothing Else.

    What Does this Input Program is ? 
    What does Language here specifically  means (Does it mean the language accepted by that particular selected encoding ?)
    What really is difference between both of them ?
    Can you definition of 2 in words like  " L is set of String ............"

     
in Theory of Computation
edited by
237 views

2 Answers

1 vote
 
Best answer

Any Language L is a set of strings inside that language.

L = {<M> | M accepts "1"} 

L is a language which contains TMs as its members such that  <M> is valid encoding of a Turing Machine and the Turing Machine M accepts "1". this language L is RE but not recursive. 

we can prove L is not recursive using Rice's theorem part-1.. L is recursively enumerable is intuitive as we can simply give M the input 1, and see if it is accepted. 

L = {<M> | L(M) = {1}} 

 <M> is valid encoding of a Turing Machine M, and it accepts only 1 as input.

this is not RE, we can prove it using Rice's theorem part-2,

Tyes is a TM which accepts a single string 1   and Tno TM which accepts two strings 1 and 2, so,. it's a non trivial property, so this is not recursive. Lets check if it is RE.

Tyes is subset of Tno, hence this property is a non-monotonic property and as per Rice's theorem part 2, it is NOT RE.

We can tell this using common sense also, suppose there is a TM M and it accepted 1 as string, but before we add it to our language L as member, we have to make sure that it doesn't accept any other strings, but we can't guarantee this as UTM will keep on running before it concludes that it accepts only one string. So it is NOT RE language


selected by
0
it's a non trivial property, so this is at least RE

Non-trivial means $L$ is not recursive -- it doesnt make the language r.e.

Also, one Tyes and one Tno is not enough to show that Tyes is not a proper subset of Tno.
0

yes, it's not REC it means either it is RE or NOT RE, isn't it?
 

"One Tyes and one Tno is not enough to show that Tyes is not a proper subset of Tno."
I am showing that Tyes is subset of Tno.

0

L = {<M> | L(M) = {1}} 

 <M> is valid encoding of a Turing Machine M, and it accepts only 1 as input.

So here <M> which is TM can only accept 1 as a string

In this

L = {<M> | M accepts "1"} 

L is a language which contains TMs as its members such that  <M> is valid encoding of a Turing Machine and the Turing Machine M accepts "1". this language L is RE.

 Do we mean that <M> which is turing machine accepts 1 as a string , but it can accept other string as well.
1 is just part of its language but it involves various other different strings in the lnaguage ?

0
yes, yogi. in fact we are not concerned about other strings, it may or may not accept. once a TM accepts 1 we can include it in our language.
0
Okay I got it .Thank you
0
@Arjun sir -:

for $L_2$, $T_{yes}$=1 and $T_{no}=1(0+1)^{+}$

$T_{Yes} \subset T_{No}$

Hence by rice thorem-2 , $L_2$ is not even Rec Enmb. ..right?
1
@manu yes, but your words were not saying so. I have edited.

@sourav Exactly.
0
sir one last doubt .. i think $L_1$ is about turing machine not about the language of R.E ...so why are we applying rice theorem on it ?
0
@arjun Complement of the second language is NOT RE too?
0
yes ,

Reasoning,  given 1 to TM and ask it accept only 1 , is Non Re since TM will be in loop after aceepting 1 also or without aceepting it also.

For compliment of L = it say TM does not accept 1, TM will be in loop even to say yes.
0
please explain why rices theorem part 2 is not applicable in first case.
0
Can someone please explain for L1 how it is RE but not REC

If we take any language it will be Tyes ..we can't find Tno

So we can't use rice theorem here...what is other way to decide RE or not ?
0
@jatin

it is a membership problem, which is a well known semi-decidable problem.
0 votes
i dont want to lag too much my answer  for both of them UNDECIDABLE

Related questions

2 votes
0 answers
1
208 views
Here is my analysis. P1: When we bound the number of steps a turing machine can tape, the total number of input possible that can be taken by such turing machine becomes finite and by running TM in an interleaved mode I can decide whether TM M halts on x within k steps. So, ... hence I can decide P3. Hence, P3 is decidable.->REC. So, I think here answer must be 1. Please let me know what's right.
asked Nov 23, 2018 in Theory of Computation Ayush Upadhyaya 208 views
0 votes
0 answers
2
105 views
L1:{<M> | there exist a Turing machine M' such that <M>$\neq$<M'> and L(M) = L(M')} How this problem becomes trivial? and if it non-trivial then please explain why is that so. According to my understanding, non-trivial properties are the one where a language ... and if it is then is it okay to say M1=M2 because they are kind of same machine but other one is just with some non deterministic nature.
asked Oct 30, 2018 in Theory of Computation Swapnil Naik 105 views
0 votes
0 answers
3
97 views
Writes Non Blank: Given a turing machine T, does it ever writes a non-blank symbol on its tape, when started with a blank tape. how the above problem is solvable? somewhere i got this explanation: Let the machine only writes blank symbol. Then its ... this is a non-trivial property of turing machine and every non trivial property of turing machine is undecidable, so this is also undecidable.
asked Sep 21, 2018 in Theory of Computation aambazinga 97 views
...