We consider languages over the alphabet = {0, 1, #}. We interpret a string w {0, 1} as a binary representation of a nonnegative integer (w). Let L = {w#x#y : w {0, 1}, x {0, 1}, y {0, 1}, and (w) = q (x) + (y) for some nonnegative integer q}. Give a low-level description of a deterministic Turing machine that decides L. (You can use a multitape model if you prefer.) Comment: When (x) > (y), q is the quotient of (w) divided by (x), and (y) is the remainder.

Is q part of the input such that you have to determine the value of the integer q? If so how do you do this in the turing machine. the length function for x and is easy to do, you just count the bits in x and y in the input tape, what I don't know how to do is multiply,add, and deterine binary numbers in a turing machine to get the expected length of w for checking. I would like to see the whole machine but at the very least a turing machine that calculates binary addition and/or multiplication, if you at least show that I can implement the rest of the overall machine. Thank you for any help and descriptions, it is much appreciated!!!!