Assignment
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) [5 marks] 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) [5 marks] 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) [5 marks] 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
Correctness
Description
Machine would work as
described
1 points
Machine may not work
on some inputs
Reasonable
made
Description is
ciently detailed
Some key steps are missing
1
suffi-
attempt
0 points
No answer provided
Very poor description or
no answer provided

Purchase answer to see full
attachment