Turing Machine for comparison

1.5k Views Asked by At

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.

1

There are 1 best solutions below

0
On

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