0
$\begingroup$

I have problems with the basics of mapping reductions.

I can understand how to do reductions using a Turing machine, but without it, I get a little bit confused.

For example:

  1. How do I do a mapping reduction from $a$ to $b$, where $a$ is $\{0,1\}$ and $b$ is $\{0\}$ over the alphabet of $\{0,1\}$?
  2. Does every language have a reduction to itself?
Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
0
$\begingroup$

The identity function is a reduction from a language to itself. One reduction from $\{0,1\}$ to $\{0,1\}$ is given by $\lfloor x/2 \rfloor$, which maps $0,1$ to $0$, and all other integers to non-zero values.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am over the Alphabet of {0,1} so for input x = 000 i need tu return an instance other then 0. tnx $\endgroup$
    – aradona
    Commented Jul 24, 2017 at 14:07
  • $\begingroup$ @aradona A suitable reduction would be a function $f$ which is defined to map 0 and 1 to 0 and any other input to 1. $\endgroup$
    – Rick Decker
    Commented Jul 24, 2017 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.