# Tally problems are x=1, binary problems are =0….

All machines must be annotated. •Tally problems are x=1, binary problems are =0. •All problems are assumed to start in standard position. But standard position is defined differently for tally and binary. Tally SP = the right most cell of the right most block. Binary SP = the right most * of the right most block. •All problems must end in standard position. • For 1-place function, the tape contains a single tally-block. For 2- place functions, it contains two tally-blocks. •All problems must end with a well-formed output: a single block, but a single block is defined differently for tally and binary. Tally block = a single block of 1’s Binary block = a block of 0’s or 1’s, flanked by *s. •All problems must end in standard position. This isn’t strictly necessary for computation, but it will be necessary to turn your machines into sub-routines. •You can use any “boxed” function that you have defined in a previous problem. Tally Problems Assume x=1. Halt in standard position. 1. Tally x+2 2. Tally 3x 3. Tally x+y For this problem, do not assume that the input blocks will be only separated by 1 cell. They may be separated by any number of cells. 4. Tally 3x+y Use the “boxes” of your solution to problems 3 and 4. You can choose the order of x- and y- blocks on the tape. 5. Tally 3(x+y) Use the “boxes” of your solution to problems 3 and 4. You can choose the order of x- and y- blocks on the tape. Binary Problems Assume x=0. Halt in standard position. 6. Binary x+1 7. Binary x–1* f(x) = x–1 if x>0 f(x) = 0 if x=0 8. Binary x+y Note: there must be a single block on the tape at the end of computation. Use the “boxes” of your solution to problems 6 and 7. General Reflection 9. Multiplication: x•y Using a combination of flow charts, prose, and “snapshots” of the tape, describe a step-by-step strategy for computing multiplication. This should not be a complete Turing Machine. (That is a difficult and laborious problem.) But it should be sufficiently detailed that you think someone could build a Turing Machine from your instructions, if they knew what they were doing.

Attachments: