I am tasked to design a turing machine which calculates the function:
$f(n) = 2n \iff 0 \le n \le 2$, or $4n+2 \iff n>2$
Where "n" is given in binary.
Now, I'm not in the slightest way sure how to do this. This is what I came up with so far:
I tried checking if a binary number is bigger than two. First, I thought that a binary number will be bigger than two if it contains more than two "1". However, this is not really the case always because 100 contains only one "1" and is bigger than two. I tried going to the end of the input string and checking the number of 1s and 0s backwards, but it ended up being even more confusing.
The only thing I have surmised until now is that if there is more than one "1", the number is surely bigger than two. That would be easy to test. Unfortunately, depending on its position, if it had only one "1", it still could be a bigger number than two.
I tried everything that popped into my mind but I'm not sure how to proceed here. Can someone give a hint, or a description of an algorithm which tests what boundary the number belongs to? I can compute the rest of the computations myself.