Consider a 2-tape Turingmachine. The problem is, given a 2-tape TM M and an inpu

Question

Consider a 2-tape Turingmachine. The problem is, given a 2-tape TM M and an input w,determine if
M even overwrite its first tape. (Whether M overwrites the secondtape does not matter.)
Formulate this problem as a language, and prove that it isundecidable. Consider a 2-tape Turingmachine. The problem is, given a 2-tape TM M and an input w,determine if
M even overwrite its first tape. (Whether M overwrites the secondtape does not matter.)
Formulate this problem as a language, and prove that it isundecidable.

Explanation / Answer

This can be simulated on a 2-tape TM ->Initially, a new set of transition functions would needto be added, nondeterministically split w into w1 and w1. Asit was being split, w1 would be copied onto tape 2 and that portionof tape 1 would be overwritten with a marker. Next, we need a set of 2-tape transition functions which allowthe simultaneous application of any TM-1 transition functions (ontape 1) and the application of any TM-2 transition functions (ontape 2). ->Then we have TM-o accept if both TM1 and TM2 accept andreject if either TM1 or TM2 reject. ->To do this we would make q-accept(TM1) and q-accept(TM2)no longer accept states. Then we would create a new acceptstate and a new transition function that connects the two previousaccept states to it. ->The TM behaves as follows: 1.String w from L is input into TM-o It is initially on tape1. 2The TM tape head 1 reads the string from left to right untilthe end. 3.TM tape head 1 reads p-n characters from w, writes them totape 2 (right to left) and overwrites those characters on tape1. 4. The TM alternately runs one transition of TM-1 on tape1 and one transition of TM2 on tape 2. This is simulated on2-tape TM by creating a set of 2-tape transition functions whichallow the application of any TM-1 transition functions to tape 1and the application of any TM-2 transition functions to tape2. 5.The TM accepts if TM1 and TM2 enter the former acceptstates.Otherwise its undecidable. ITS HELPFUL TO YOU.......

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.