Markov algorithm for computing $f(x) = x$ mod $3$? As the question title suggests, what is a Markov algorithm for computing the function $f(x) = x$ mod $3$?
 A: 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.
