1. Give a formal definition (state diagram) of a Turing machine M that computes the negation of a signed binary number (in 2’s complement format) on the tape.
a) if the input is empty, M loops.
b) if the input number is positive, M accepts leaving the 2’s complement on the tape.
c) if the input number is negative, M rejects leaving the absolute value on the tape.
d) if the input is 00...0, M accepts leaving 10...0 on the tape.
For example, if the initial tape is 011010, the Turing machine should accept and leave 100110 on the tape. If the initial tape is 101110, the Turing machine should reject and leave 010010 on the tape.
2. Give an implementation-level description of the Turing machine M defined above