Turing Machines Homework

1. Unary numbers, as described in the lecture are represented by a number of tallies equal to the number. For example 3 is represented as |||. Subtraction of a unary numbers is done by removing one tally from the left hand side for each tally in the right hand side. Thus ||| − || ≡ || − | ≡ |. Write a Turing Machine that performs unary subtraction.
2. Binary numbers are represented by zeros and ones which each have a place value. Each place represents a power of two. Subtraction on binary numbers is done by subtracting individual digits and resolving 'carrying' as needs be. This is very similar to base ten subtraction learned in elementary school. For example 11111 − 0000 = 11111 and 10101 − 1111 = 00110. Write a Turing Machine to subtract a 4 bit binary from a 5 bit binary number.