Markov algorithm for computing $f(x) = x$ mod $3$?

Question

As the question title suggests, what is a Markov algorithm for computing the function $f(x) = x$ mod $3$?

Answer 1

Let us represent $x$ and $f(x)$ in binary notation. If I am not mistaken, the following Markov algorithm should compute $f(x)$ \begin{align} 00 &\to 0 &&(1) && \text{delete $0$ in the front of the input}\\ 01 &\to 1 &&(2) && \text{delete $0$ in the front of the input}\\ 11 &\to 0 &&(3) && \text{since }11xxx\cdots \equiv 0xxx\cdots \pmod 3\\ 100 &\to 1 &&(4) && \text{since }100xxx\cdots \equiv 1xxx\cdots \pmod 3\\ 101 &\to 10 &&(5) && \text{since }101xxx\cdots \equiv 10xxx\cdots \pmod 3 \end{align} For instance, if $x = 1101101010$ (874 in decimal), the algorithm will give \begin{align} 1101101010 &\xrightarrow{(3)} 001101010 \xrightarrow{(1)} 01101010 \xrightarrow{(2)} 1101010 \xrightarrow{(3)} 001010 \xrightarrow{(1)} 01010\\ &\xrightarrow{(2)} 1010 \xrightarrow{(5)} 0100 \xrightarrow{(2)} 100 \xrightarrow{(4)} 1 \end{align} It is tempting to replace (1) and (2) by $0 \to \varepsilon$ and (3) by $11 \to \varepsilon$, where $\varepsilon$ is the empty word. However, I wish to get only $0$, $1$ or $10$ as possible outputs.