Give an implementation leveldescription of a TM

L = {x=y ⊕ z|x, y, z are binary integers, and x is the XOR of y and z}

is non-regular, i.e., no FA exists that could recognize the language. How can I give an implementation level description of a TM that decides on L?

1 Answer

There is an important gap between human reasoning ("high level") and the formal definition of a Turing Machine ("low level"). If you are approaching these exercises for the first time and you are not yet familiar with TMs, what I recommend is to write down a pseudocode description of the algorithm which is nothing more than a high level description of the Turing machine itself) and then to "break up" the algorithm into smaller entities, until the transition function of the machine is achieved.

In the case of your example you can consider $$x$$, $$y$$ and $$z$$ as binary encodings of integers, then you need a function that does the following:

1. Read the input $$(x$$, $$y$$, $$z)$$
2. Compute $$y \oplus z$$
3. Compare $$(y \oplus z)$$ to $$(x)$$

If the equality in point 3 is verified, accept the language. This TM will always accept membership in your language $$L$$.

• You can also avoid explicitly computing the XOR. – Yuval Filmus Oct 21 '19 at 18:26