1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ @rici If the first 1 is at the end of the number, doesn't that mean that the number is, 001? $\endgroup$
    – john doe
    Jun 19, 2022 at 8:17
  • $\begingroup$ @johndoe Is $\sqcup00010\sqcup $ a valid input on the tape for $2$? I mean the leading zeros. (I assume the most significant bit first.) $\endgroup$
    – John L.
    Jun 19, 2022 at 13:26
  • 1
    $\begingroup$ Fixing the typo in previous comment: A binary number is less than or equal to 2 iff the first $1$ is either at the end of the number or is followed by a $0$ which is at the end of the number, or If there's no first $1$. In the last case, the value of the number is 0 and the function you're asked to implement returns the number, so you can stop there. The "rest of the computations" consist only of appending $0$ or $10$ at the end. $\endgroup$
    – rici
    Jun 19, 2022 at 13:50
  • $\begingroup$ rici's approach is nice. I wrote a slightly different approach in my answer. $\endgroup$
    – John L.
    Jun 19, 2022 at 16:49

1 Answer 1

Reset to default
0
$\begingroup$

Instead of just checking "if a binary number is bigger than two", check whether the input is 0, 1, 2 or "big", where "big" means greater than 2.

Assume the most significant digit in the input is to the left.

Let the Turing machine (TM) read the input from left to right, remembering the value of the binary number read so far, which is 0, 1, 2 or big. In other words, "0", "1", "2" and "big" will the possible states while the TM is reading the input.

The state transitions are quite easy. For example, reading 0 will update state "1" to "2". For example, "big" will always result in "big".

Once the blank symbol is encountered, the TM will write 0 if the state is not "big", which means $n\to 2n$, and write 1 and then 0 otherwise, which means $n\to 2n+1\to4n+2$.

; Run the following code at https://morphett.info/turing/turing.html.
; Solve https://cs.stackexchange.com/questions/152480

; Machine starts in state 0.
; Always moves to the right.
; Never overwrites the input.

; <current state> <current symbol> <new symbol> <direction> <new state>
; * means the new symbol is the same as the current symbol.

0 0 * r 0
0 1 * r 1

1 0 * r 2
1 1 * r big

2 0 * r big
2 1 * r big

big 0 * r big
big 1 * r big

; _ is the blank symbol.
0 _ 0 r halt
1 _ 0 r halt 
2 _ 0 r halt
big _ 1 r 1_appended
1_appended _ 0 r halt
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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