[Math] Turing Machine for comparison

computer scienceturing-machines

If one wants to design a Turing Machine for a function such as this:

Function

In other words, f(x; y; z) is a projection function which returns either y (if
x = 0) or z (if x = 1). For other values of x; f returns 1 (an "error").

How would I erase the elements that I don't need? For example, if x=0 I only want to have y on tape, and if x = 1 have z on tape and erase the rest.

A test input to try could be: f(0; 00; 000). The numbers on tape will be in unary notations. (0 is the empty string, 1 = 0).

I am getting lost at the erasing part maybe i am wondering if some could help me out.

Best Answer

First you need to get clear on how exactly you are going to represent the numbers on the tape. You say to use unary notation ... but your example is a little confusing:

A test input to try could be: f(0; 00; 000). The numbers on tape will be in unary notations. (0 is the empty string, 1 = 0).

I'll propose to use a string of $n$ 1's to represent the number $n$, and to have a B (Blank) between the numbers. Also, to disambiguate the 'error' output from 1, I'll use an 'e' symbol for error. Finally, I'll assume the machine starts at the leftmost 1 of x (or at the B where x is supposed to be if x = 0), and I'll have the machine halt at either the leftmost 1 of y, or the leftmost 1 of z, or on the symbol e, depending on which condition applies.

If you want to change this convention for your purposes, I assume that should be an easy change, but with this convention, here is a machine that does what you want:

enter image description here