Turing Machine: Accepting Palindromes Using One Tape

by

🌿 1. Palindrome — A Quick Reminder

A string is a palindrome if:

  • reading it from the left gives the same sequence
  • as reading it from the right

For example:

  • 0000 ✓
  • abcba ✓
  • 01010 ✓
  • 0110 ✗ (not the same both ways)

🌿 2. The Challenge for a One-Tape Machine

Humans can see the whole string at once.
A Turing Machine, however:

  • sees only one symbol at a time
  • moves step by step
  • has no direct access to the “last” character

So it must be clever.
Instead of comparing characters right away, it does something like this:

Take the outermost characters → check if they match → remove them from consideration → repeat.

🌿 3. The Core Strategy (Explained as Simply as Possible)

Here’s the idea the Turing Machine follows:

🔸 Step A — Pick the left character

Go to the leftmost unmarked symbol (either 0 or 1).
Replace it with a temporary mark like X, meaning “this symbol has already been processed.”

🔸 Step B — Walk all the way to the right

Move right, cell by cell, until you reach blank space at the end of the input.

Move one step left — now you’re on the last character.

🔸 Step C — Compare

If the rightmost character matches the one you picked earlier, mark it too (X).

If it doesn’t match, the machine rejects the string instantly.

🔸 Step D — Return to the left side

Move left until you reach the next unmarked symbol.

Then repeat the whole cycle.

🔸 Step E — Stop when everything is checked

If all symbols have been marked or only one symbol remains, the string is a palindrome → accept.

This is similar to peeling the outer layers of an onion—one layer from the left, one layer from the right, until nothing is left.

🌿 4. How the Tape Looks During the Process

Suppose the input is:

a  b  b  a  B  B  B ...
^
(head on first symbol)

After the machine checks the first and last characters:

X  b  b  X  B  B  B ...
           ^

After checking the middle pair:

X  X  X  X  B  B  B ...
         ^

When everything is converted to X, the machine accepts the input.

🌿 5. Breaking the Algorithm into Phases

The entire behavior can be thought of as four mini-tasks:

1️⃣ Find the next left unmarked symbol

  • Read it
  • Remember what it was by entering a particular state
  • Mark it as X

2️⃣ Travel to the far right

  • Move right until you find a blank
  • Step back one cell

3️⃣ Check and mark

  • If the symbol matches what you remembered → mark it
  • Otherwise → reject

4️⃣ Return to the left

  • Go left until the next unmarked symbol appears
  • Repeat

This cycle continues until the string is fully “peeled away.”

🌿 6. A Gentle Analogy

Imagine you have a row of cards placed face up on a table.
To test symmetry:

  • You pick the left card
  • Then walk to the right end and pick the right card
  • If they are identical, you discard both
  • Otherwise, you stop — it isn’t symmetric

A Turing Machine follows the same philosophy, but with symbols on tape instead of cards.

🌿 7. Simplified State Diagram

Below is a conceptual flow that illustrates how the Turing machine moves between tasks (not a complete formal diagram):

   +-----------+
   |  q_start  |
   +-----------+
        |
        v
   [Find left symbol]
        |
        v
  +---------------+
  | q_mark_left   |
  +---------------+
        |
        v
  [Move to right end]
        |
        v
  +----------------+
  | q_check_right  |
  +----------------+
        |
   match? | mismatch?
        |       |
        v       v
  q_mark_right  q_reject
        |
        v
  [Return left]
        |
        v
     q_start

When there are no more unmatched symbols:

q_start → q_accept