Lower Bound for One-Tape Turing Machine for Recognizing Palindromes       

Mathematics Accomplishment | 1966

IBM researcherAlan Cobham

Where the work was doneIBM T.J. Watson Research Center

What we accomplished: Cobham showed that a one- tape Turing machine could not recognize a palindrome in linear time. In the process he invented the crossing sequence argument, which is one of our key tools in proving lower bounds.

Related linksA. Cobham, Time and Memory Requirements for Machines Which Recognize Squares and Polyndrons Yorktown Heights IBM Research Report RC-1621 (1966). Citation.

Image credit: The graph shows time of solution of problem in milliseconds (msec) vs. problem size, n, for knapsack problems solved by a state-of-the-art specialized algorithm using a 933 MHz Pentium III computer (average of 100 instances, data from:[6]). The fit of the quadratic equation suggests that empirical algorithmic complexity for instances with 50–10,000 variables is O((log n)2) despite having exponential worst-case complexity estimate in theory. By Cngoulimis - Own work, Public Domain