Give a detailed description of a Turing Machine M which halts on every input and, when given a string x element {0, 1}*, accepts if and only if there are strings y, z elemet {0,1}* and a non-negative integer n such that |y| = |z| = n and x = y1^n z. Your Turing Machine must not alter any blank tape squares. That is, your machine is free to write over the contents of the tape containing the input, but it is not allowed to write any symbol to a blank tape square other than coproduct. In your description of M please give A detailed description of the tape alphabet P (if you use any extra tape characters), giving the purpose of each extra character you introduce beyond sigma U {coproduct}. A detailed description of the movement of the rcad-writc head on an arbitrary input. Note that 1^n = 11....1 and 1 degree is the empty string