Turing Machine: Accepting Palindromes Using One Tape
🌿 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_startWhen there are no more unmatched symbols:
q_start → q_acceptAbout the Author
