trivial reduction for undecidability in complexity theory.

15 Views Asked by At

Can the reduction if $w \in A$, then we red(w) for all w mapped to a constant element which we know $red(w) \in B$ and similarly for $w \notin A$ we map to a single different $red(w) \notin B$? This seems like a trivial way to reduce problems to find undecidability? For example:

def red(M, w):
     if M(w):
        return "def g(x): \n dummy = 0 \n return x"
     else:
         return "def g(x): return x"

a proper reduction of L_univ to A := {f | f is a program such that when running f("zero"), an instruction of the form = 0 is executed, where is some variable} ?

We do have in the end that $w \in L_{univ} \iff f(w) \in A$