[FOM] Computability question

[Robert Lubarsky]

If a language is undecidable, so is its complement. Yet both the union  and
the intersection of those two are decidable.

Bob Lubarsky


-----Original Message-----
From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of
Daniel Schwartz
Sent: Friday, February 10, 2017 9:26 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