f(x,y)=ceiling((x+y)/2) and x1, y1 is given.

Note: The ceiling function of a real number is the least integer number greater than or equal to the given number. In the case of 4.5, the integers greater than 4.5 are 5, 6, 7, 8, .. The smallest of all is 5, and hence ceiling(4.5)=5.

Build a Turing Machine that calculates the function given above.

The initial configuration of the tape is given below:

000....00111.....1....

x zero's y one's

The final configuration of the tape is given below:

AAA....AAAAA.....Aaaaaa....aa....

x A's y A's

ceiling(f(x,y)) NOTES: The position of the read/write head is not important when the machine halts.

Do not assume that there is a blank at the begining of the input.