[FOM] Computability question
Ben Sherman
sherman at csail.mit.edu
Sat Feb 11 12:16:27 EST 2017
You're right: undecidable languages aren't closed under either binary union or binary intersection. Here is a simple class of counterexamples:
Given an undecidable language L, its complement Lc is also undecidable. Then the union of L and Lc is the trivially true subset, which is decidable, and the intersection of L and Lc is the trivially false subset, which is decidable.
> On Feb 11, 2017, at 12:06 PM, fom-request at cs.nyu.edu wrote:
>
> From: Daniel Schwartz <schwartz at cs.fsu.edu <mailto:schwartz at cs.fsu.edu>>
> Subject: [FOM] Computability question
> Date: February 10, 2017 at 9:25:51 PM EST
> To: fom at cs.nyu.edu <mailto:fom at cs.nyu.edu>
> Reply-To: Foundations of Mathematics <fom at cs.nyu.edu <mailto:fom at cs.nyu.edu>>
>
>
> 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 <mailto:schwartz at cs.fsu.edu>
> U.S.A. http://www.cs.fsu.edu/~schwartz <http://www.cs.fsu.edu/~schwartz>
> ************************************************************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170211/759d7f9b/attachment.html>
More information about the FOM
mailing list