Design a Turing machine that receives a positive integer and adds 1 to it, as follows. The symbols for your Turing machine are the ten digits 0, 1, 2, 3, . . ., 9, and the default character *. Caution: this is a little different from what we did in class. Since the digit 0 has a specific meaning in the input and the output, we choose something else to be the default character. The Turing machine receives a positive number digit by digit, and adds 1 to it. For example, if the input is 1 0 7, the output should be 1 0 8. If the input is 9 9, the output should be 1 0 0. Sample Input 1 S1 1 0 7 Sample Output 1 HALT 1 0 8 Sample Input 2 S1 9 9 Sample Output 2 HALT 1 0 0 You will need to define a set of states, and for each state, you will need to list the instructions. Assume that you begin in state S1, and that the input is to the right of the initial position of the head, as shown above. Briefly describe what each state does see the Turing Machine notes and the Lecture 3 slides for examples. 2