76 citations · 440 across the 53 of their papers we have counts for
7 papers · 1 filter
Effective bi-immunity and randomness
Achilles A. Beros, Mushfeq Khan, Bjørn Kjos-Hanssen
We study the relationship between randomness and effective bi-immunity. Greenberg and Miller have shown that for any oracle X, there are arbitrarily slow-growing DNR functions rela…
Few paths, fewer words: model selection with automatic structure functions
Bjørn Kjos-Hanssen
We consider the problem of finding an optimal statistical model for a given binary string. Following Kolmogorov, we use structure functions. In order to get concrete results, we re…
Models of the Chisholm set
Bjørn Kjos-Hanssen
We give a counter-example showing that Carmo and Jones' condition 5(e) may conflict with other conditions on the models in their paper \emph{A new approach to contrary-to-duty obli…
Automatic complexity of shift register sequences
Bjørn Kjos-Hanssen
Let be an -sequence, a maximal length sequence produced by a linear feedback shift register. We show that has maximal subword complexity function in the sense of Allouch…
On the complexity of automatic complexity
Bjørn Kjos-Hanssen
Generalizing the notion of automatic complexity of individual strings due to Shallit and Wang, we define the automatic complexity of an equivalence relation on a finite…
Permutations of the integers induce only the trivial automorphism of the Turing degrees
Bjørn Kjos-Hanssen
Let be an automorphism of the Turing degrees induces by a homeomorphism of the Cantor space such that preserves all Bernoulli measures. It is proved that must…
Constructing a weak subset of a random set
Bjørn Kjos-Hanssen, Lu Liu
The tree forcing method given by (Liu 2015) enables the cone avoiding of strong enumeration of a given tree, within a subset or co-subset of an arbitrary given set, provided the gi…