I'm currently learning about polynomial reductions in my computational models course, and there's this reduction which I cant wrap my head around:
We're given the language $ L=\{{<M,w> | w\circ w \in L(M) \iff w\in L(M)}\}$
My tutor has shown me the following reduction from $NOT-ACCEPT$, but I cant seem to understand it despite him trying to explain it.
$NOT-ACCEPT \leq _m L$
$<M,w>\rightarrow _R <M',w'=w>$
$R(<M,w>):$
$M'(x):$
$if\ x=w, reject\\if \ x=w\circ w, output\ M(w)\\ else, \ do \ something(for \ example,\ reject)$
And his explanation was:
Note that for (M', w) to be in L, L(M') needs to behave the same on w and w\circ w. If (M,w) in NOT-ACCEPT then both w and w \circ w either reject or go to an infinite loop, which means they look the same to L, as required
In the other case, M' treats w and w\circ w and differently, thus it is not in L.
Which I cant really understand how this works, assuming $<M,w>\in NOT-ACCEPT$ we can expect that if $x=w\circ w$ then the output $M(w)$ would simply be "reject", thus rejecting $w\circ w$ but not $w$.
I could use some clarifications on this.