Nullifying randomness and genericity using symmetric difference

https://doi.org/10.1016/j.apal.2017.03.004Get rights and content
Under an Elsevier user license
open archive

Abstract

For a class C of sets, let us say that a set A is C stabilising if AXC for every XC. We prove that the Martin–Löf stabilising sets are exactly the K-trivial sets, as are the weakly 2-random stabilising sets. We also show that the 1-generic stabilising sets are exactly the computable sets.

MSC

primary
03D32
secondary
68Q30
03D28

Keywords

K-trivial sets
Algorithmic randomness

Cited by (0)

1

The first author was partially supported by John Templeton Foundation grant 15619: “Mind, Mechanism and Mathematics: Turing Centenary Research Project”.

2

The second author was partially supported by grant #358043 from the Simons Foundation.