A "Game Semantical" Intuitionistic Realizability Validating Markov's Principle
Federico Aschieri, Margherita Zorzi · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2014
We propose a very simple modification of Kreisel's modified realizability in order to computationally realize Markov's Principle in the context of Heyting Arithmetic. Intuitively, realizers correspond to arbitrary strategies in Hintikka-Tarski games, while in Kreisel's realizability they can only represent winning strategies. Our definition, however, does not employ directly game semantical concepts and remains in the style of functional interpretations. As term calculus, we employ a purely functional language, which is Goedel's System T enriched with some syntactic sugar.