Q1. A high-level description follows: The main idea is that x*y is equivalent to adding x to itself y times. We use M+ as a blackbox for dyadic addition. The TM will first verify input to be of the proper form as described in the specification, rejecting otherwise. If the input is valid, the TM adds x to a running total z a total of y times. To control the number of times the addition is performed, we have a second running total S that is initialized to 0 and incremented by 1 every time we add x to z, and we stop once S is equal to y. The addition of x to z is only performed AFTER verifying whether S=y. Implementation Level (In what follows, let b represent the blank symbol. We use 3 tapes in our TM) On input w... 1. Verify that input is of the correct form as outlined in the specification. To do so, we scan the input for the existence of exactly one instance of 'X'. If we do not find exactly one X symbol, REJECT after moving the tapehead over the first symbol of w. 2. Knowing that the input is of valid form, we use a second tape to hold the running total S, initialized to 0. However, the second tape will always have the form #S (i.e. a # symbol in its first cell). 3. We write #y to the third tape for comparison purposes with tape 2. 4. We fix the first tape to hold bx#0. That is, this first tape will hold a blank symbol, followed by a copy of x, followed by a separator #, and followed by our running total for x*y (initialized to be 0). This tape will serve as input to M+ as it conforms to the proper input form. 5. If the contents of tape 2 and tape 3 are equal, we are done. To finalize the computation, we must change the contents of tape 1 from bx#z, where z is our running total, to bz, and have the tapeheads over the first symbol of z. This is done by shifting all symbols following # left a total of |x|+1 cells. We now ACCEPT, otherwise continue to step 6. 6. Copy "+x" to the end of the first tape's contents. Note that the tape now holds bx#z+x, where z is our active running total (initialized to be 0 at first). 7. Give the first tape to M+, returning with tape contents bx#v, where v=z+x in dyadic notation. This completes one addition of x to our running total z. 8. We copy +1 to the end of tape 2, now holding #S+1. We feed this to M+, returning with an incremented counter i.e. tape 2 now contains #T, where T=S+1 in dyadic notation. This indicates that we have added x to our running total once more. We now loop back to Step 5. Q2a) Suppose L is decidable and let M_L decide it. We create a decider for L' was follows: On input x... 1. for i=0...|x| 2. Copy the first i symbols of x to a second tape. 3. Send the second tape as input to M_L. If M_L rejects, REJECT. Otherwise, continue. 4. next i 5. ACCEPT. Now, suppose the above machine accepts a string x. This happens iff M_L accepts each prefix of x (each string consisting of the first i symbols of x, over all i). Finally, M_L accepts each prefix iff each prefix is in L. Now suppose the machine rejects a string x. This happens iff there exists some i such that the first i symbols are not accepted as input to M_L. This means some prefix of x is not in L. By definition, x is therefore not in L'. Q2b) We claim that L' is recognizable but not necessarily decidable. The above machine suffices as a recognizer. One notes that it may loop on step 3 since M_L may loop on any input. Q3. Refer to the given model as an i-step model. We first show that any i-step model can be simulated by the standard model using a doubly infinite tape and a second tape. The second tape holds an incrementing counter that records what step of the computation we are on. The standard model follows the same transitions as the i-step model (in terms of what it does to the tape), but its movements are dictated by the number written on the second tape: if the i-step model moves right, the standard model moves right a number of times specified by the value on its second tape. After each such series of moves, the standard model increments the value on the second tape which indicates that we have continued to the next step of computation. With the second tape initialized to 1, the movements of the standard model directly correspond to the movements of the i-step machine, and by construction the tape modifications (if any) are identical. Note that although states need not be mentioned at implementation-level, even the state transitions are almost identical, though states need to be introduced in order to move the tape head as a function of the second tape's contents. This shows that any i-step machine can be simulated by a standard machine, and hence the former have no further language recognition abilities than the latter. We now show the other direction: every standard model machine can be simulated by an i-step machine. Note that movement to the right for the standard model's tape head is equivalent to one movement to the left followed by one movement to the right in the i-step model (mathematically, this is really i movements to the left and i+1 movements to the right, equivalent to one movement to the right). A similar relation is found for left head movements. It immediately follows that tape head movements can be simulated. Our only concern is ensuring that if the standard model moves off the left-hand side of the tape, our i-step model must not move into the negative side of its doubly infinite tape. To prevent this from happening, we may mark the lefthand side of the tape with a unique symbol # such that if we ever land on #, we know we have moved into the negative portion and so we move the tapehead back to the right one cell. Again, although not necessary for implementation level, very little is to be said for the state transitions. We may introduce new "dummy" states that simply move the tapehead right or left and transition into a fixed state based on construction. However, this detail is not necessary. So we have showed any computation by the standard model can be simulated by the i-step model, hence standard models have no more language recognition abilities than the i-step models. Therefore, the two models are equivalent.