The Gateway to Computer Science Excellence
+2 votes
133 views
Define languages L0 and L1 as follows :

L0={⟨M,w,0⟩∣M halts on w}

L1={⟨M,w,1⟩∣M does not halt on w}

Here ⟨M,w,i⟩is a triplet, whose first component M is an encoding of a Turing Machine, second component w is a string, and the third component i is a bit.

Let L= L0 ∪ L1. Which of the following is true?

L is not even recursively enumerable as we cannot even design an acceptor for L as even when L0 is RE L1 is not RE

but can anyone explain me what about L COMPLEMENT what is the language ??
closed as a duplicate of: GATE2003-54
in Theory of Computation by Active (3.8k points)
closed by | 133 views
0
Why is L1 not RE?
0
I suppose you learned this wrong reason for L1 not being r.e. from some bad material. Suppose $A$ and $B$ are non r.e. languages. Are you saying that $A \cup B$ is also not r.e.?
0
i  didn't say L1 union L2 is not re if L2 is not re as a part of the language is halting Turing machine problem when u simulates the above inputs which are encodings of Turing machines on a universal turing machine we cannot even say YES to inputs of L2 hence we cannot even make a acceptor for language L thats what i meant L is not recursively enumerable now please tell me why L complement is not RE
0
You can never tell part of a language is "undecidable" this is nonsense. So I cannot tell anything for what you asked. And this question is answered in the link given -- but if you have such wrong concepts with you you won't be getting it.
+1
i didnt say a part of the language is undecidable i said the whole language is undecidable because a part of it if solved makes the halting problem decidable if we can say L1={⟨M,w,1⟩∣M does not halt on w} "for a given M and for a given w if we can say M never halts on w we can say that this is a solution to halting turing machine problem " hence this part of the whole problem is not even RE this makes the entire problem NOT RE because we cant even design an acceptor for the problem as a whole i am speaking about the reduction but in informal way which anyone can understand
0
Nice - that works. So, now you should surely get the explanation given in the link for $L'$
0
sir i know the concept before itself what i am asking is if we take the complement of L in form of set notation which is L1' intersection L2'  which can be even a empty set right ? how can we gaurentee that the intersection in this case in nonempty set and please explain how this set is generated i am unable to understand that part please help
0
Without taking complement, what will be $L_1 \cap L_2$?
0
it will be set of turing machine encodings which halt on w  and set of encodings which wont halt on w                             so will this be a empty set ?
0
If so under what condition will be the intersection of their complements produce empty set?
0
as there are no machines which halt and not halt on the same input w   wont intersection be null or am i thinking it wrong ?

Related questions

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
50,737 questions
57,385 answers
198,557 comments
105,368 users