1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You're probably going to need to include a state that has a loop to itself that replaces the 0 with a blank and moves the tape head to the right. $\endgroup$
    – benguin
    Mar 31 '17 at 23:21
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.