Problem 4. (Deciding Even/Odd Input Length with TMs) For this problem you need to write the full definition of a Turing Machine T which, given a binary input string b, accepts if the length of the input string b is even length and rejects if b has an odd length (that is, use g, to indicate an even input length and g, to indicate an odd length). So for example, if the input to T is the string 01101 your TM should run and eventually halt in state g, indicating an odd length for input 01101. (i) Write out the 7 parts of your Turing Machine (TM) and specify the full program, i.e. show the details of each of the 7 parts clearly and specify the full program by writing all of the states and 5-tuples used by T. Hint: To help you you should look at the TM described in Example 3.7 (page 171) of the Sipser's textbook but a lot shorter and easier. Still, you are writing the details of a full TM (see page 169 for what the details are) and so it takes some work. You need not justify what you write in this part. (ii) Show how TM T would work on the input string 101111