29 citations · 29 across the 1 of their papers we have counts for
Showing math.LOShow all
2 papers · 1 filter
math.LO2017
Normalized Information Distance and the Oscillation Hierarchy
Klaus Ambos-Spies, Wolfgang Merkle, Sebastiaan A. Terwijn
We study the complexity of approximations to the normalized information distance. We introduce a hierarchy of computable approximations by considering the number of oscillations. T…
math.LO2014★ 29 cited
Comparing DNR and WWKL
Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp +1
In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL (weak weak König's Lemma).