¿Algoritmo de Markov para calcular $f(x) = x$mod $3$?

Question

Como indica el título de la pregunta, ¿qué es un algoritmo de Markov para calcular la función $f(x) = x$mod $3$?

Answer 1

Nos representan $x$ y $f(x)$ en notación binaria. Si no me equivoco, debe calcular el siguiente algoritmo de Markov $f(x)$ $$\begin{align} 00 &\to 0 &&(1) && \text{delete %#%#% in the front of the input}\ 01 &\to 1 &&(2) && \text{delete %#%#% 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}$$ por ejemplo, si $0$ (874 en decimal), el algoritmo le dará\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 {Alinee el} es tentador sustituir (1) y (2) $0$ y (3) $x = 1101101010$, donde $0 \to \varepsilon$ es la palabra vacía. Sin embargo, deseo obtener sólo el $11 \to \varepsilon$, $\varepsilon$% o $0$ como salidas posibles.