-1

I have been tasked to create a mapping reduction from a decidable language to the Halting problem and also prove it. I'm absolutely stumped, any help is appreciated.

Andrés E. Caicedo
  • 79,201
Ervin Enriquez
  • 11

1 Answers1

0

I'm assuming that a mapping reduction is a computable function $f$ such that $x\in L$ iff $f(x) \in H$ (I know this as a many-one reduction). Tell me if you mean something different or if you don't understand the conventions I use below.

Fix your decidable language $L$, and the halting problem $H$. Let $P$ be the procedure that decides $L$, and let $Q$ be any procedure that never halts. We now define $f$:

On input $x$, compute $P(x)$. If $x\in H$, return the code for $P(x)$. If $x\notin H$, return the code for $Q(x)$.

Now, you need to show that $f$ is computable and that $x\in L$ iff $f(x)\in H$.

James
  • 5,443
  • Would P and Q basically be a verifier? Like this https://cs.stackexchange.com/questions/93878/verifier-complexity-theory – Ervin Enriquez Dec 02 '19 at 00:03
  • You will have to translate what I put there into your formalism. Both $P$ and $Q$ are processes that decide certain problems for you. If your class/text uses verifiers, then they are verifiers. – James Dec 02 '19 at 00:07