2021/01/29 by Merlin Carl, Carl, Merlin, Lorenzo Galeotti +3
Computer Science · #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2101.12656
openalex publication_date 2021/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.