The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
35 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 (22.5k points) | 35 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 (3.3k 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

37,963 questions
45,465 answers
131,321 comments
48,375 users