# Lower Bound for One-Tape Turing Machine for Recognizing Palindromes

**Mathematics Accomplishment |** **1966**

** IBM researcher: **Alan Cobham

**Where the work was done**: IBM 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 links**: A. 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

BACK TO IBM RESEARCH ACCOMPLISHMENTS