Wednesday, April 27, 2011

Why recursive languages are NOT closed under homomorphism

Refer to this slide.

First let's consider a much simpler problem, inverse homomorphism, in which w is in L' if and only h(w) is in L. We can just apply h to w and let the TM accepting L run with input h(w). So L' is recursively enumerable(resp. recursive) if L is recursively enumerable(resp. recursive).

Now we'll attack homomorphism, in which w is in L' if and only if for some x, both h(x)=w and x being in L hold.

For recursively enumerable languages, the slide say that we can design an NTM M to take as input w, guess an x such that h(x)=w and simulate M1 on x(suppose L=L(M1)). I will give a detailed sketch on how M behaves. It
0)sets l to 1
1)guesses one x of length l
2)if there is such an x invokes M1 otherwise goes to 4)
3)if M1 accepts so would M otherwise goes to 4)
4)increases l by 1 and goes back to 1)
So if L is recursively enumerable, so is L'.
And of course we can use a DTM that generates each x in a systematic way.

Now what about recursive languages? Even though L is recursive, the above process may not halt since there may be infinitely many x'es such that h(x)=w but none of these x'es is in L.

At last, I will give an example in which for every w, there are infinitely many x'es such that h(x)=w. Consider the function h: N*N->N in which h(a,b)=a. Of course, {x|h(x)=w}=N for every w in N. And N*N is countable, as is explained in this slide.

P.S Since every TM(either deterministic or nondeterministic) has a corresponding encoding, it is possible to "design" different NTM's(as sub-routine) for different input strings, as is the "break" operation in the discussion of concatenation. Even though potential break positions are infinite, for every specific string they are finite.

P.S This page gives a concrete example for exercise 9.2.6(e).

No comments:

Post a Comment