ex1: selected solutions

2. a. No. The tape alphabet must contain symbols that are not in S as 
otherwise it would be impossible to tell when the input ends (every 
cell would accommodate a valid character of the alphabet).
 b. A machine can start by moving left once, twice, or three times, or not 
move left at all, and immediately after move to the right. This means that 
the heada could be in any of location 1/2/3/4 (where location 1 denots the 
starting position). To describe a single machine exhibiting any of these 
behaviours, consider a machine that reads the character (number) on the first
cell of the tape, and according to it will decide how many times to move left
as desribed above. This is possible simply by decreasing this number by one 
until it is zero and then it will start moving right.

3. high level: The machine will perform a loop where at each iteration it will
 compare character in position i with that of position L+1-i, for 
i=1...floor(L/2), and reject at any point if the character in the 
i'th position is 0 and the character in the L+1-i position is 1. At 
the loop termination of the loop accept.
 implementation level: check the first character. Cross it out and go to the 
end of the string (before the first crossed out symbol) and read the symbol 
there. If the first of these two is 0 and the second one, reject. Cross out
that symbol and move left until hit a cross out symbol, and then one to the 
right, and repeat.  If at one point after crosing out the next character is 
also crossed out, accept.