--- title: "TM configuration; TM for palindromes" subject: "Theory of Computation" chapter: 4 key: "semester_3/theory_of_computation:tm-config-palindrome" source: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-config-palindrome site: BCT Engineering --- # TM configuration; TM for palindromes Theory of Computation · Chapter 4: Turing Machine - Asked in: 2070 Chaitra - Video: [Turning Machine for all Palindromes || Even & Odd || Length | TOC || FLAT| Theory of Computation](https://www.youtube.com/watch?v=zGzKegl_JDQ) — Sudhakar Atchala - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/tm-config-palindrome - Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4 ## Question Define the term configuration of a Turing machine. Design a Turing machine which accepts the set of all palindromes over the alphabet {0,1}*. ## Short answer A configuration records state, tape, and head position, like u q a v. The TM for palindromes erases first symbol, moves to last to check equality, erases it, repeats, and accepts if empty or one symbol remains. ## Answer #### Configuration of a Turing machine A **configuration** (instantaneous description) records everything needed to continue a computation: the current state, the tape contents, and the head position. It is written as a triple (q, u, a v) or as the string **u q a v**, where q is the state, u the tape contents to the left of the head, and a v the contents from the scanned symbol a onward (trailing blanks omitted). One move gives the relation ⊢. The start configuration for input w is q0 w, and w is accepted if q0 w ⊢* (a configuration in an accepting state). Example: the configuration 10 q2 1 means the tape holds 101 with the head on the last symbol, in state q2. #### TM for palindromes over {0,1} **Idea.** Erase the first symbol, remember it, go to the last symbol, and check it equals the remembered one; erase it and repeat. If the string becomes empty (even length) or exactly one symbol is left (odd length), accept; otherwise reject. States: q0 start; q1 / q3 go right remembering 0 / 1; q2 / q4 check the last symbol; q5 return left; qa accept. | State | Read | Write | Move | Next | |---|---|---|---|---| | q0 | ⊔ | same | S | qa | | q0 | 0 | ⊔ | R | q1 | | q0 | 1 | ⊔ | R | q3 | | q1 | 0 / 1 | same | R | q1 | | q1 | ⊔ | same | L | q2 | | q3 | 0 / 1 | same | R | q3 | | q3 | ⊔ | same | L | q4 | | q2 | 0 | ⊔ | L | q5 | | q4 | 1 | ⊔ | L | q5 | | q5 | 0 / 1 | same | L | q5 | | q5 | ⊔ | same | R | q0 | | q2 | ⊔ | same | S | qa | | q4 | ⊔ | same | S | qa | The only difference from the wwᴿ machine is the two rules q2/q4 on ⊔, which accept when the middle symbol of an odd palindrome is left alone. #### Examples - 010: q0 erases 0 and goes right; the last symbol 0 matches and is erased; q0 now reads 1, erases it, finds nothing to the right, and q4 reads ⊔, so it accepts. - 0110: two rounds of matching 0-0 and 1-1, then q0 reads ⊔ and accepts. - 01: the last symbol is 1 but 0 was remembered; no move exists, so it halts without accepting. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does a configuration of a TM record? A. Only the current state B. State, tape contents and head position C. Only the tape D. The transition table Answer: B. A configuration u q a v gives state q, tape contents and the scanned symbol. (Key point: Configuration) 2. What do the extra rules q2/q4 on blank do? A. Reject B. Accept when the middle symbol of an odd palindrome is left alone C. Move right D. Erase the tape Answer: B. When one symbol remains, the check state meets a blank and accepts. (Key point: Odd palindromes) 3. How does this machine differ from the w w^R machine? A. It uses extra tapes B. Only in the two rules for q2 and q4 reading a blank C. It starts at the right D. It writes x and y marks Answer: B. Adding those two accepting rules extends even palindromes to all palindromes. (Key point: Difference from wwR) 4. Why does the machine reject 01? A. The last symbol 1 differs from remembered 0, so no move is defined B. Length is even C. It loops D. q0 reads blank Answer: A. q2 expects 0 or a blank, but sees 1, and halts without accepting. (Key point: Rejecting 01) ## Related in Theory of Computation - [PDA for palindromes over {a,b}](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-palindrome-ab) — Theory of Computation, chapter 3 - [Multitape TM as copying machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-copy) — Theory of Computation, chapter 4 - [TM for aⁿcbⁿ (single tape, deterministic)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-an-c-bn) — Theory of Computation, chapter 4 - [Define multitape Turing machine](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-multitape-define) — Theory of Computation, chapter 4 - [What is a Turing machine; its operation](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-define-operation) — Theory of Computation, chapter 4 - [How a universal Turing machine works](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Auniversal-tm-example) — Theory of Computation, chapter 5 ## Related in other subjects - [Taper turning: set-over and compound angle](https://www.bctengineer.com/question.md?key=semester_2%2Fworkshop_technology%3Ataper-turning-setover-numerical) — Workshop Technology, chapter 6 - [AI, Turing test, CSP examples](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Aturing-test-pass-csp-examples) — Artificial Intelligence, chapter 1 - [Six-speed machine tool gearbox design](https://www.bctengineer.com/question.md?key=semester_7%2Fmachine_design_ii%3Amachine-tool-speed-ladder-gear) — Machine Design II, chapter 5 - [Initial line design for 200 MW over 120 km](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Aline-design-200mw-120km) — Transmission and Distribution System Design, chapter 2