Randomising Realisability

DOI10.1007/978-3-030-80049-9_8MaRDI QIDQ6359376arXivFDO

Authors Merlin Carl, Lorenzo Galeotti, Robert Paßmann

Publication date 29 January 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-80049-9_8

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

math.LO

Abstract: We consider a randomised version of Kleene's realisability interpretation of intuitionistic arithmetic in which computability is replaced with randomised computability with positive probability. In particular, we show that (i) the set of randomly realisable statements is closed under intuitionistic first-order logic, but (ii) different from the set of realisable statements, that (iii) "realisability with probability 1" is the same as realisability and (iv) that the axioms of bounded Heyting's arithmetic are randomly realisable, but some instances of the full induction scheme fail to be randomly realisable.

This page was built for publication: Randomising Realisability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6359376)