  Intuitionistic first-order logic extended with a restricted form of Markov's
principle is constructive and admits a Curry-Howard correspondence, as shown by
Herbelin. We provide a simpler proof of that result and then we study
intuitionistic first-order logic extended with unrestricted Markov's principle.
Starting from classical natural deduction, we restrict the excluded middle and
we obtain a natural deduction system and a parallel Curry-Howard isomorphism
for the logic. We show that proof terms for existentially quantified formulas
reduce to a list of individual terms representing all possible witnesses. As
corollary, we derive that the logic is Herbrand constructive: whenever it
proves any existential formula, it proves also an Herbrand disjunction for the
formula. Finally, using the techniques just introduced, we also provide a new
computational interpretation of Arithmetic with Markov's principle.
