The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
32 views

If L1 and L2 are Turing-Recognizable then L1 ∪ L2 will be decidable???

can i say L1 and L2 is re and re is closed under union operation so it is decidable??

asked in Theory of Computation by Boss (12.7k points) | 32 views
0
$L_{1}=RE$

If $L_{2}=RE$and complement of $L_{1}$ then only it will be decidable
0
RE $\cup$ RE = RE
If $\bar{L1}$ and $\bar{L2}$ are also RE then only their union is Decidable i.e Recursive

1 Answer

0 votes
I THINK NO BECAUSE DECIDABLE MEANS total turing machine i.e REC

AND REL IS SEMIDECIDABLE BECAUSE IS RECOGNISED BY TURING MACHNIE NOT BY TOTAL TURING MACHINE
answered by Active (1.9k points)


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

35,484 questions
42,741 answers
121,445 comments
42,135 users