HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Find an undecidable language that is mapping-reducible to its complement

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
undecidablereduciblelanguageitsthatfindcomplementmapping

Problem

As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All_{TM}, EQ_{TM}, T$ (that is the set of all deciders) satisfy this property. But I tried reducing these to their complements directly, and via some sort of intermediate language, but to no avail. Can anyone help?

Solution

Another more advanced answer is to look at a complete problem from a class that is closed under complement. For example, take the arithmetical hierarchy which is closed under complements. Now consider a complete problem for it like:


Given: a sentence in the language of first-order arithmetic,

Question: is the sentence true (in the standard model $\mathbb{N}$)?

It is easy that one can reduce this to its complement by negating the sentence.

This works generally for any class that is closed under completion and has a complete problem (w.r.t. many-one reductions).

Context

StackExchange Computer Science Q#6100, answer score: 2

Revisions (0)

No revisions yet.