We will adopt the following input-output conventions for calculating a function on a number, from the Standford Encylopedia of Philosophy, except that we replace the \"0\" in their representation with \"B\" in our representation.) In the examples that follow we will represent the number n as a block of n+1 copies of the symbol '1' on the tape. Thus we will represent the number 0 as a single '1' and the number 3 as a block of four '1's. We will also have to make some assumptions about the configuration of the tape when the machine is started, and when it finishes, in order to interpret the computation. We will assume that if the function to be computed requires n arguments, then the Turing machine will start with its head scanning the leftmost '1' of a sequence of n blocks of '1's. the blocks of '1's representing the arguments must be separated by a single occurrence of the symbol 'B'. For example, to compute the sum 3+4, a Turing machine will start in the following configuration, where the ellipses indicate that the tape has only blanks on the cells that we can't see, and the upward arrow indicates the cell that is currently scanned. B B A machine must finish in standard configuration too. There must be a single block of '1's on the tape, and the machine must be scanning the leftmost such '1'. If the machine correctly computes the function then this block must represent the correct answer. So an addition machine started in the configuration above must finish on a tape that looks like this: ... B 1 1 1 1 1 1 1 1 B ... In addition, if the Turing machine is used to decide whether a number is in a given set of numbers, the input convention is the same, but the output convention is that the readwrite head stop over a square in which either a special symbol \"yes\" has been written, or a special symbol \"no\" has been written. 1. Draw the annotated graph of a Turing Machine that outputs n-1 if n is 1 or greater, and 0 otherwise. (15) a. 2. An algorithm that lists all of the theorems of a theory does something intuitively less difficult than does an algorithm that, for every sentence, correctly decides whether or not the sentence is a theorem of a theory. Suppose, however, that you had a procedure that lists all the theorems of a theory T and that you had another procedure that lists all the sentences that are not theorems of that same theory T. Explain how these two listing procedures could be used together to form a procedure that, for every sentence, decides whether or not the sentence is a theorem of T. (10) a. 3. Why is every recursive set recursively enumerable? (5) a. 4. Consider any axiomatizable first-order theory T with axiom set A. A sentence S is a theorem of T if and only if there is a proof of S from A. There is an algorithm that effectively lists all of the proofs from A. Explain why the set of theorems of T is recursively enumerable. (Hint: consider the relation between a theorem T and a proof S of T.) (10) a