Construct a Turing Machine which tests if a given character string consisting of only zeros and ones is a palindrom.



Example of palindroms

Initial condition

The character string is bounded by #-symbols on both sides. The read/write-head starts on the left #-symbol.

Final condition

If the input is a valid palindrom, the Turing Machine has to halt in an empty world. If the input string is not a palindrom, the world may not be empty at the upon termination.