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.

The Gateway to Computer Science Excellence

+2 votes

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

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

L is set of String & each String is an Encoding of TM & TM accepts 1**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 ............"

+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

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.

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

@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?

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?

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 ?

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,059 comments

104,692 users