[jasmas]

I have a question about the arbitrary memory test and palindromes. Are we talking about the memory required to test? Or the memory required to hold the string? The only memory required to test a palindrome should be that for two characters because you only need compare the first and last character and continue toward the middle so long as those match. If you end up with 0 or 1 characters remaining and all previous comparisons have matched then the word is a palindrome. It doesn't seem that different to me than possibly infinitely testing if the next character is still an A in the case of (A*)

[yeputons]

The memory required to test. Moreover, we do not have random access to the string, we may only read one byte at a time and cannot go back. You may call it "streaming access".

More formally, we're talking about finite automata: https://en.wikipedia.org/wiki/Deterministic_finite_automaton