[FOM] Computability question
Kreinovich, Vladik
vladik at utep.edu
Fri Feb 10 23:31:42 EST 2017
Easy: if a language is decidable then its complement is also decidable, same algorithm but change yes to no and vice versa.
Let's take any non-decidable language A, its complement -A is thus also non-decidable. However, the union of these two sets is the whole set of natural numbers and the intersection is an empty set, both are decidable. So here are examples of non-decidable sets whose union and intersection are decidable.
An example when the union and intersection of two non-decidable sets are not decidable is even easier: take any non-decidable set A and take B = A, then both intersection and union are equal to A and are, thus, undecidable
________________________________________
From: fom-bounces at cs.nyu.edu <fom-bounces at cs.nyu.edu> on behalf of Daniel Schwartz <schwartz at cs.fsu.edu>
Sent: Friday, February 10, 2017 7:25 PM
To: fom at cs.nyu.edu
Subject: [FOM] Computability question
Dear FOM list,
Would anyone know the answer to the following?
It is well known that the decidable languages are closed with respect to
union and intersection. What about the undecidable languages?
I'm guessing that these are not closed with respect to either union or
intersection, since I have been unable to find proofs, but I don't know of
any counterexamples.
Any light that anyone can shed on this would be appreciated.
Dan Schwartz
************************************************************************
Dr. Daniel G. Schwartz Office 850-644-5875
Dept. of Computer Science, MC 4530 CS Dept 850-644-4029
Florida State University Fax 850-644-0058
Tallahassee, FL 32306-4530 schwartz at cs.fsu.edu
U.S.A. http://www.cs.fsu.edu/~schwartz
************************************************************************
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom
More information about the FOM
mailing list