Is there a counterexample or theorem for the question below?

Examples:

Let's look at some examples first to get the feel of it. We'll let $n$ be the length of the input in characters. All the examples are recognizers that aren't intended to produce any output other than "accept" or "reject".

1. Linear search. We're given a sequence of characters. An input character is read; if it matches what is searched for, we terminate with success. If not, that input can be thrown away since it doesn't match and we go on to the next character in the input.

2. Deterministic context-free parsing. An input word is read and either shifted onto the stack or reduced with the existing stack, to form a new stack. Since the parser is just a recognizer, we don't have to remember the original input word once it has been reduced into a nonterminal.

3. Final character matching. This is an artificial example to clarify the question. The format is $n-1$ input characters that don't matter and a final character that does. If the final character matches a fixed constant character, we succeed, otherwise we fail. Again, we can simply throw away all non-final characters as they're read since they don't matter.

In each case, gradual progress is being made toward a solution each time an input is read, where "gradual progress" is a gradual transformation of the machine configuration into a final state such that at some step during the transformation, enough information is lost to make it impossible to reconstruct the original input: that is, the computation becomes irreversible to the extent that it is impossible to reconstruct the original input. Is the following paragraph true for every polynomial-time recognizer? Is there a theorem to back it up? Or is there a counterexample?

Question:

(Notation: L is a language in P, and M is a polynomial-time recognizer for L.) For all L there exists an M (subject to the constraints below) where there is progress (defined above) during the computation. More precisely, there is no L in P such that for every constrained (see below) M for L there is no progress during the first $n-1$ characters of the computation and then a "sudden flash" that produces the answer on encountering the final input character.

We are given two constraints:

1. Irreducibility. There is no polynomial-time reduction from a "sudden flash" machine to a gradual one, so we can't just create a wrapper machine which batches up the inputs and at the end simply passes it to a gradual machine to actually carry out the computation.

2. Incompressibility. We are also given that there is no polynomial-time compression transformation of an input $n$ characters in length to a size substantially less than linear: that is, of a complexity class less than $O(n)$; see example 3 above (this gets rid of highly redundant examples).

EDIT: In one of the comments I suggested a proviso; this is no longer necessary. In the case of string matching, I mentioned that there is an algorithm which simply throws away initial characters as long as they match, thus providing irreversibility. In the case of a constant test string, I had suggested a finite-state solution, but this is not necessary since there is simply a polynomial-time reduction to the first string matching strategy in this paragraph. So the proviso I suggested is withdrawn; the question stands.

-
You mean example 3 above? – joriki Jul 11 '11 at 20:28
I'm not sure I understand the question correctly. What if we're trying to determine whether the entire input matches a certain string? At each point, the input can be reconstructed, since the fact that the process hasn't terminated implies that the input so far matched the string. Am I missing something? – joriki Jul 11 '11 at 20:39
@joriki: Thanks for the clarification. If one is matching against a string, one can just throw away the corresponding initial characters if they match. If the string is constant, the problem is just finite-state, so the state/configuration doesn't have to hold it. I should have added the proviso that the information is actually encoded into the machine configuration, and not just logically derivable. As for your earlier question, I'll need more explanation. Thanks – ShyPerson Jul 11 '11 at 21:12
I meant that in constraint 2 you say "see example 4 above" but there are only examples 1 to 3 and you seem to be referring to example 3? – joriki Jul 11 '11 at 21:20
@joriki: Yes, sorry, that should be example 3. Thanks – ShyPerson Jul 11 '11 at 21:26

I think a counterexample is provided by a polynomial-time recognizer of reversed initial sections of some normal sequence whose initial sections can be computed in polynomial time, for instance the decimal digits of the Champernowne constant or, presumably, the hexadecimal digits of $\pi$ ("presumably" because it's not known, though widely believed, that these form a normal sequence). In trying to decide whether a given input is such a reversed initial section, the entire input has to be stored until the end is reached, since there is no way of knowing which parts of the sequence to compare the input to before the end is reached, and all possible finite patterns occur infinitely often in a normal sequence, so it can never be excluded that what's been seen so far could be the beginning of one of the reversed initial sections; whether it is always potentially depends on a single piece of the input already seen.