CSSE 474: Day 3

Topics

• Language
• Deciding vs recognizing a language
• Two-track TMs
• TMs with two-sided infinite tape

Homework

1. Consider bullet item (2) from the proof of Theorem 3.13, p. 149. The author gives a sketch of the how to simulate a multi-tape TM through a single tape TM. Let's be more specific.

   Write the transition function for a single Tape TM which simulates the following double tape TM. Sigma={A,B,X,Y}, Tau={A,B,X,Y,_,#}, delta={<q0, [A,_], q0, [A,_], [R,S]>, <q0, [B,_], q0, [B,1], [R,R]>}. This TM counts the number of Bs on the input tape and writes that number in unary on the storage tape. Assume that X is A with a dot on top of it and Y is B with a dot on top of it. Please follow the prescribed algorithm of first sweeping to the right and then back left.

2. Exercise 3.8 from page 160 and problems 3.12 and 3.15(d) from page 161.

   Feel free to work on this assignment in pairs. This assignment is due by Monday, Dec. 5th, 8am. For part (1) You need to submit a .txt file that we can paste into the TM simulator applet.