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

Show that the Halting problem is reducible to its complement

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

Problem

HALT$_{TM}$ is the set of all machine-input pairs $ $ where $M$
halts on input $w$


The complement of HALT$_{TM}$ is the set of all machine-input pairs
$ $ where $M$ doesn't halt on input $w$


Show that HALT$_{TM}$ is turing reducible to its complement, and
explain why it's impossible for it to me many-one reducible.

Regarding the Turing reduction, I've made reduction proofs using using A$_{TM}$ and HALT$_{TM}$ but this doesn't make sense to me intuitively.

I understand the concept of many-one reduction using the Oracle, but have difficulty applying it, not being given any examples to work with.

I'd hugely appreciate it if someone could help me approach the above question, I'm more concerned with the approach rather than the answer, as I've an exam tomorrow!

Thanks a lot.

Solution

Suppose $HALT$ was many one reducible to $\overline{HALT}$. Let the mapping function be $f$. We construct a machine $D$. It takes input $\langle M,w \rangle$ obtains the string $f(\langle M,w \rangle)=\langle M^{'},w^{'} \rangle$. $D$ simulates $ M$ on $w$ and $M^{'}$ on $w^{'}$. If the first simulation ends $D$ accepts if second simulation ends/halts it rejects. $D$ is a decider for $HALT$ which is not possible.

Context

StackExchange Computer Science Q#54111, answer score: 6

Revisions (0)

No revisions yet.