Computable smallness is not intrinsic smallness

Abstract: We construct a set $A$ that is computably small but not intrinsically small. To understand these terms, we liken $A$ to a game show host playing against a class of computable contestants, analogous to an infinite variant of the Monty Hall problem. The host has infinitely many doors arranged in a line, and each door hides either a goat or a car. A contestant selects infinitely many doors to open and wins if a non-zero density of the selected doors hides a car. Contestants that are disorderly can select doors out of order, opening door $i$ after door $j>i$. Are disorderly contestants more difficult to beat than orderly ones? This is known to be true if contestants are allowed to be adaptive, where they may choose a different door depending on the outcomes of the previously opened ones [1] (via the theorem that MWC-stochasticity 0 does not imply Kolmogorov-Loveland-stochasticity 0). We give a constructive proof to show that the statement also holds in the non-adaptive setting, shedding light on a disorderly structure that outperforms orderly ones. This is joint work with Justin Miller.

[1] Merkle, Wolfgang and Miller, Joseph S and Nies, Andre and Reimann, Jan and Stephan, Frank. Kolmogorov--Loveland randomness and stochasticity. Annals of Pure and Applied Logic, vol.138 (2006), no.1-3, pp.183--210.

logicprobability

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic