  We address the problem of simulating an arbitrary binary interactive
first-order Markovian protocol over a pair of binary symmetric channels with
crossover probability $\varepsilon$. We are interested in the achievable rates
of reliable simulation, i.e., in characterizing the smallest possible blowup in
communications such that a vanishing error probability (in the protocol length)
can be attained. Whereas for general interactive protocols the output of each
party may depend on all previous outputs of its counterpart, in a (first-order)
Markovian protocol this dependence is limited to the last observed output only.
Previous works in the field discuss broader families of protocols but assess
the achievable rates only at the limit where $\varepsilon\to0$.
  In this paper, we prove that the one-way Shannon capacity,
$1-h(\varepsilon)$, can be achieved for any binary first-order Markovian
protocol. This surprising result, is to the best of our knowledge, the first
example in which non-trivial interactive protocol can be simulated in the
Shannon capacity. We give two capacity achieving coding schemes, which both
divide the protocol into independent blocks, and implement vertical block
coding. The first scheme is based on a random separation into blocks with
variable lengths. The second scheme is based on a deterministic separation into
blocks, and efficiently predicting their last transmission. The prediction can
be regarded as a binary pointer jumping game, for which we show that the final
step can be calculated with $O(\log m)$ bits, where $m$ is the number of rounds
in the game. We conclude the work by discussing possible extensions of the
result to higher order models.
