[Math] Why isn’t there a pumping lemma for recursively enumerable languages

Question

I'm studying the theory of computation, and I know there are pumping lemmas for regular and context-free languages, but why not for recursively enumerable languages? Is there something about a Turing machine that would make a pumping lemma impossible? My guess is that no matter how you pump a string, a Turing machine can always recognize it, but I am uncertain.

Answer 1

Part of the problem is that TMs are allowed to go backwards through their tapes. This makes concocting a Pumping Lemma difficult for a basic reason.

Recall that the basic proof of the Pumping Lemma for regular languages was to take a DFA $D$ for $L$, and then count the number of local configurations (the numbers of states multiplied by the size of the alphabet). If $D$ reads any string in $L$ of length greater than this, then there must be a (state,symbol) pair which is reached two times. By "pumping" the substring that appears between the times $D$ in in these two states, the definition of a DFA makes it clear that $D$ must do the exact same thing each time through each of these pumps.

For PDAs the reasoning is similar.

Note that if you attempted to do the same for a TM $M$ you would run into a problem since it could have been that the steps between reaching the same (state,symbol) pair you read a symbol to the left of that substring. Then the pumping may not work because moving to the left at a pump may result in a different action being taken (because there is no guarantee that the last symbol of this pumped substring is the same as the last symbol before this pump, and you might have to take into account even earlier symbols, just compounding the problem). So not only would a proof of a Pumping Lemma have to take into account the local (state,symbol) configuration, but actually the full configuration would be needed. In this way the set of configurations that need to be distinguished becomes unbounded, and so the pigeonhole argument fails.