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 M₁ on x(suppose L=L(M₁)). 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 M₁ otherwise goes to 4)
3)if M₁ 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).

SRM502 Div1 Level2 500 Problem

We define the relation problem[i]<problem[j] if pointsPerMinute[i]*requiredTime[j]>pointsPerMinute[j]*requiredTime[i]. This is a total order, as is explained in this thread.

If two adjacent problems, say i and i+1, satisfies that problem[i+1]<problem[i]. Then by swapping them, we get a better solution, for doing so doesn't affect the points of all other problems, increases problem[i+1]'s point by pointsPerMinute[i+1]*requiredTime[i] and decreases problem[i]'s point by pointsPerMinute[i]*requiredTime[i+1]. By definition, the former is larger.

Many people figure out at this point that the best solution must be exactly the one satisfying problem[i]<=problem[i+1] for all i in the range [0,n-2], e.g. this post by wywcgs. I used to just believe so after a USACO contest, but now I'm not that convinced. So I do some careful analysis.(I hope for an intuitive explanation.)

Lemma 1. If S is not a sorted sequence, then there must be at least one pair of adjacent elements such that S[i]>S[i+1].
Lemma 2. For every possible sequence S, we can get the sorted sequence by repeatedly swapping adjacent pairs such that S[i]>S[i+1]. We know in linear algebra such adjacent swapping reduces the inversion number by exactly 1.(I'm eagerly looking forward to a more elegant explanation.)
Theorem 3. The sorted sequence is the best solution. This comes directly from the fact that all the swapping operations in Lemma 2 increase the points.

Note that we may not want to include some problems, since their points may become negative. But every time we do decide to include a problem, it must be placed at the end if we consider the problems in order. So the optimal substructure and independent substructure properties are reserved. The recurrence relation becomes obvious as in the classic 0-1 knapsack problem: best[i][j]=max(best[i-1][j], best[i-1][j-requiredTime[i]]+maxPoint[i]-j*pointsPerMinute[i]). Here i means we have so far considered problem [0, i] and j means the last problem gets solved at time j.

P.S. See Petr's perfect code here.