Describe a Turing Machine that accepts if the XOR of the first two binary numbers is equal to the third binary number and rejects otherwise. Note: You just need to describe how the TM would function as we have done in lectures. You do not need to specify the TM
1. Consider the problem of conputing the XOR of two binary and determining if the result is equal to a third binary number. Suppose the input tape contains three binary numbers, separated by $ symbols. Each binary number consists of one or more bits with one bit per cell. E.g.,
# 0 1 1 0 $ 0 1 0 1 $ 0 0 1 1 # #
(a) Describe a Turing Machine that accepts if the XOR of the first two binary numbers is equal to the third binary number and rejects otherwise. Note: You just need
to describe how the TM would function as we have done in lectures. You do not need
to specify the TM in full. Feel free to describe a multi-tape Turing Machine if that is
easier.
(b) [5 marks] Describe a Random Access Machine that accepts if the XOR of the first two
binary numbers is equal to the third binary number and rejects otherwise. Note: You
just need to describe how the RAM would function as we have done in lectures.
2. Consider the problem of checking if an XOR of n binary numbers is equal to 0. The input
tape contains n binary numbers, separated by $ symbols.
(a) Describe a Turing Machine that accepts if the XOR of the binary numbers
is 0. Note: You just need to describe how the TM would function as we have done in
lectures. You do not need to specify the TM in full. Feel free to describe a multi-tape
Turing Machine if that is easier.
(b) Describe a Random Access Machine that accepts if the XOR of the binary
numbers is 0 and rejects otherwise. Note: You just need to describe how the RAM would
function as we have done in lectures.
Marking Scheme
Marking scheme for Question 1a, 1b, 2a, and 2b.
3 points 2 points 1 points 0 points
Correctness Machine would work as
described
Machine may not work
on some inputs
Reasonable attempt
made No answer provided
Description Description is suffi-
ciently detailed
Some key steps are miss-
ing
Very poor description or
no answer provided