• Site Map

• Lectures

• Homework

• Tests/Exam

• Main Webpage

Homework Assignment 1

Due: by 6pm on Wed 30 Jan
Worth: 8%

For each question, please write up your answer carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

1. Write a one-tape enumerator with the following behaviour: when started with a blank input tape, your enumerator will "print" the binary representations of multiples of 5 one after another. Each binary representation should have no leading 0's — in particular, the number 0 is represented by the empty string ε, which translates to having nothing at all on the tape of the enumerator.
   Recall that an enumerator "prints" a string by writing it on its tape and going to a special state q_print (or q_P, for short). Your enumerator should never stop, printing one multiple of 5 after another. Note that by convention, the behaviour of your enumerator when its tape is not initially blank can be anything at all, i.e., do not bother to deal with this case explicitly. Also, recall that your enumerator is allowed to use additional symbols in its tape alphabet.

   Give a high-level description of your enumerator (one short paragraph giving the main idea(s) of your algorithm), an implementation-level description of your enumerator (broken down into numbered stages that describe head movements and tape contents in more detail), and a formal-level description of your enumerator (the input and tape alphabets, and full transition diagram or table, broken down into sections with comments to explain the purpose of groups of states and relate them to the implementation-level stages).

2. A "right-bound" TM is like a regular TM except that at each step, the head may only stay put (S) or move right (R) — there is no left move.

   Prove or disprove that right-bound TMs are equivalent to regular TMs. Write a detailed, implementation-level answer. (If you attempt a proof, you may use any variant of TMs that was shown to be equivalent to regular TMs in class.)

3. A "k-head" TM is like a regular TM except that it has k independent read-write heads (each head is numbered, from 1 to k) and it allows "stay-put" (S) head movement. Initially, all heads start on the leftmost square. At each computation step (each transition), the current state and k symbols read by the heads determine the next state, k symbols written by the heads, and k directions of head movements, with the convention that heads write in the order k, k-1, ..., 2, 1. This convention specifies what happens if multiple heads attempt to write different symbols on the same square: the lowest-numbered head writes "last" and determines the symbol that ends up on that square. For example, if a 3-head TM is in state q₆ with heads 1 and 3 on the same square that contains an 'a' and head 2 on a different square that contains a 'b', and if δ(q₆,a,b,a) = (q₄,b,L,b,R,a,S) (meaning head 1 writes a 'b' and moves left, head 2 writes a 'b' and moves right, and head 3 writes an 'a' and stays put) then the square that was scanned by heads 1 and 3 will contain a 'b' at the end of this transition.

   Prove or disprove that k-head TMs are equivalent to regular TMs. Write a detailed, implementation-level answer. (If you attempt a proof, you may use any variant of TMs that was shown to be equivalent to regular TMs in class.)

4. Prove that every finite language is decidable. Do this by arguing directly about Turing Machines, i.e., you may not make use of the fact that all regular languages are decidable.