# 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.

BINARY

Consider the problem of computing 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.

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.

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.