Why we can't reliably test for palindromes on one pass

Question

I came across the concept of "palindrome". I try to understand by reading through wikipedia

http://en.wikipedia.org/wiki/Palindrome#Computation_theory

The paragraph caughts my attention

This means that it is impossible for a computer with a finite amount of memory to reliably test for palindromes on one pass.

I thought to test whether a given string is "palindrome" is pretty straight forward? I came out a quick code.

public class Utils {
    private static final String SPECIAL_CHARACTERS_REGEX = "[\\s!,]";

    private static String removeSpecialCharacters(String string) {
        return string.replaceAll(SPECIAL_CHARACTERS_REGEX, "");
    }

    public static boolean isPalindrome(String string) {
        String str = string.toLowerCase();
        str = removeSpecialCharacters(str);

        if (str.isEmpty()) {
            return false;
        }

        int head = 0;
        int tail = str.length() - 1;
        while (head < tail) {
            char h = str.charAt(head);
            char t = str.charAt(tail);

            if (h != t) {
                return false;
            }

            head++;
            tail--;
        }

        return true;
    }
}

It seems to work fine at first glance.

public static void main(String[] args) {
    String s = "";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // false

    s = "1";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true

    s = "12";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // false

    s = "123";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // false

    s = "taco cat";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true

    s = "A man, a plan, a canal, Panama!";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true

    s = "Amor, Roma";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true
}

If so, may I know why the wikipedia states that it is impossible to test for palindromes on one pass? Am I overlook something?

Answer 1

The problem is not checking whether a string already in memory is a palindrome. If you can get the string into memory, the check can be done easily, but you've already used up the one pass by reading the string into memory, so the check is the second pass.

But that will only work if the entire string fits into memory. Since the premise is that memory is finite, it means you cannot verify whether strings which are longer than the capacity of memory are palindromes, which is what the sentence you quote is saying.

By contrast, there are lots of checks you can do with finite memory on arbitrarily long strings. For example, you can check whether the string's length is divisible by 5. You can check if every a in the string is immediately followed by a b. In general, you can check if the string matches any regular expression (here, I mean regular expression in the mathematical sense, as opposed to the patterns recognized by "regular expression" libraries.) But since you cannot describe the set of all palindromes using a regular expression, you cannot verify in a single pass that an arbitrarily long string is a palindrome, using only a finite amount of memory.