3. A Big Headed Turing Machine (BHTM) is just like an ordinary Turing machine, b

Question

3. A Big Headed Turing Machine (BHTM) is just like an ordinary Turing machine, but with the ability to read and write two adjacent tape symbols in one step. It moves left or right one cell at each step, as before. a) 15 ptel Explain why BHTMs are no more powerful than ordinary Turing machines. b) [5 ptsl For w E (0,1)*, let SORT(w) be the sorted rearrangement of w, in which all the O's precede the 1's. For example, SORT(10110) = 00111. Explain how a BHTM can compute the SORT function. You don't have to describe your Turing machines completely, but give enough detail that a com petent Turing Machine programmer could implement them.

Explanation / Answer

A normal Turing machine at any one time, the machine has a head which is positioned over one of the squares on the tape. With this head, the machine can perform three very basic operations:

Read the symbol on the square under the head.
Edit the symbol by writing a new symbol or erasing it.
Move the tape left of right by one square so that the machine can read and edit the symbol on a neighbouring square.

But a Big headed Turing machine has the ability to write two adjecent tape symbols in one step. Hence its operations are faster compared to a normal Turing machine.

SORT Function
A. The starting state; also used to restart the sort after swapping the initial 1 and 0.
B. This state "remembers" that the last character examined was 0.
C. This state "remembers" that the last character examined was 1. Thus if the next character seen is a zero (0) a swap is necessary; we know that the character to be in this position after the swap will be 1 and thus it is inserted into the tape now.
D. A swap is in process (the state was changed to D from C) and thus a 0 will appear here, but continue to look left (i.e. move the tape right).
E. The state does most of the work! State E is used while looking left on the tape to see whether a 0 needs moving further to the left. If a 1 is seen above the E then then we know that the character to the right is 0 and needs swapping with this character, so move the tape right one space and go to state C. If a 0 is found then continue to look to the left (i.e. move the tape right). If we get to the left-hand end of the tape (*) then we restart the sort from the item to the right in state A.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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