Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

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.

share|improve this answer

The reason is that context free and regular languages are recognized by much simpler kinds of automata that have limitations on how they use their memory, while a Turing machine does not have those limitations.

For example, a regular language is recognizable by a finite state machine. The finite state machine has no memory at all, apart from knowing what state it is in. So, if you run a finite state machine long enough, it must enter the same state twice. But, since it has no way to tell it has been in that state before, it has no way to tell if it has been in that state twice, five times, or a thousand times. This is the way the pumping lemma for regular languages is proved - we can trick the finite state machine by making it go through several more steps that leave it in the same state it was in originally, and it has no way to tell that this has happened.

The pumping lemma for context free languages is similar. These are accepted by pushdown automata. The limitation on the memory of a pushdown automaton is that the automaton can only look at the top element of the stack - it cannot tell how deep the stack is below that top element. We can use this limitation to trick the automaton by adding or removing information from the stack, keeping the top element the same. The automoaton cannot ask how deep the stack is, so it has no way to tell we have changed it.

Recursively enumerable languages are accepted by Turing machines. A Turing machine has no limitation on how it can use its tape memory. It can record every step that it takes, and look back over all those steps at any time. So there is not any way that we can trick the Turing machine in the way we can trick a finite state machine or pushdown automaton.

share|improve this answer

Suppose I have $L = \{ <M>,w :$ M is a TM that halts on w $\}$. This is clearly recursively enumerable. It's not regular though, nor is it context free. The pumping lemmas for regular and context free languages tell you that if you have a string in the language, building the string but maintaining the pattern will keep the new string within the language.

So if I have a FSA, I can simply keep looping or going back and forth between a couple states to build up a string of desired length. Regular languages are context free grammars, so the intuition is the same. A Turing Machine is more sophisticated in what it can accept. Keep in mind that programming a Turing Machine is like writing machine code (not assembly, but machine code).

share|improve this answer

A Turing machine can decide languages like the set of all strings that consist of $N$ substrings that are each consecutive 0's and consecutive 1's that alternate where the substrings have length $1,2,3,..,N$, for some natural number $N$ (the language is the union over all possible $N$). It's hard to imagine any kind of pumping lemma that could handle such a language.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.