CS Language theory help

Supposed answer:

http://cseweb.ucsd.edu/classes/wi00/cse105/hw5sol.pdf go to problem 4(b)

Doesnt make sense though, from what they claim, my Language L = {0} can be mapping reducible to its complement L' which is an infinite set consisting of everything apart from 0.

Other things in L' as mentioned in the OP are impossible to map to, so how is this a valid mapping reducible function?

anybody? willing to paypal for an explanation just trip your post

>>8972980
The answer is false, but youre answer is incorrect.

I don't think you understand the language thing quite yet. Your L(TM) = {0}, but it mapping reductions are for all instances of the languages, not just mapping accepted strings to accepted strings. So we can construct a mapping reduction from L to solve L' by just negating yes/no.

A simple counter example would be to propose a TM that accepts all strings over a language, such the it's compliment is empty

>>8973042
The reason we can't map to the empty set is because theres no strings in the Language, we can't transform a string into an instance of the language

>>8973056
The important thing about a mapping reduction is that for L1 <m L2, we transform every instance of L1 into an instance of L2, but the mapping does not have to be one-to-one.

This is where your answer fails. Since I'm bored I'll give the Turing machine
M
1 on input w runs TM on w
2 if TM accepts, output 1
3 if TM rejects output 0

>>8973042
>>8973056
>>8973066

Im not getting it, by mapping reducibility everything in L' must be mapped to by some element in L, you say it doesn't have to be one-to-one but this just means that f(0) -> Everything in L' for my example, how can this be true?

Im a brainlet so can you explain to me why exactly you are able to create a function that maps something in L to an element such as 010 or 110 or 111111 thats all in L'?

Im so confused, this shouldn't be possible

>>8973110
>by mapping reducibility everything in L' must be mapped to by some element in L
No. Everything in L must map to something in L'.

For yours we create the function
f:
f(0) = 1
f(<not zero>) = 0

This satisfies the mapping reduction, since all instances of L are transformed into and instance of L', and all accept strings are still accept strings in the end mapping, same for rejects

File: 1234.png (65KB, 628x558px) Image search: [Google]

65KB, 628x558px

>>8973146
I see, if it is only one directional then I understand. But I thought the "iff" implies both ways, pic related from sipsters book, I guess I understand now why the arrows in the picture is one directional.

Would A <=m B imply B <=m A? I suppose using my same example I could take B and construct the function

f:
f(1) = 0
f(<not 1>) = 1

Similarly?

Im still a bit stumped on the significance of the "iff" for all these years I thought I understood bi-conditionals, I don't know if its the frame of thought im in which is why im thinking about it wrong but I can't seem to shake off the fact that we only need to show everything in L maps to something in L' and not the other way too..

Sorry if its a bit long

>>8973164
The bidirectional in this case just enforces that all elements in A map to something in B, and that all elements in B that the function maps to comes from A. If that helps understand what it means.

>Would A <=m B imply B <=m A
No. If we show A <m B, all that it says is that B is at least as hard as A, since if we can solve B, we can solve A. But there are no guarantees the other way.

E.g.
We can reduce L:{0*1*} to the halting problem, but we couldn't reduce the halting problem to L.

>>8973175
One last question, could maybe say a little of the intuitive idea behind reducing? Like you say L = {0*1*} is reducible to the halting problem, but the halting problem cant be reduced to L, so this must mean that L is much harder to solve than the halting problem? I think I am making some bad assumptions because of the english word "reducing" I somehow think that by A <m B somehow B is an easier problem to solve than A because its """reduced""" when that isnt true as youve said.

But apart from that yes your comments have helped me alot thank you