Kučera och Gács visade självständigt att varje oändlig sekvens är Turing reducible till en Martin-Löf slumpmässig sekvens. Detta resultat förlängs genom att visa att varje oändlig sekvens S är Turing reducible till en Martin-Löf slumpmässig sekvens R sådan att det asymptotiska antalet bitar av R som behövs för att beräkna n bitar av S, dividerat med n, är exakt den konstruktiva dimensionen av S. Det visas att detta är den optimala kvoten av frågebitar för att beräkna bitar som kan uppnås med Turing minskningar. Som en tillämpning av detta resultat, en ny karakterisering av konstruktiv dimension ges i termer av Turing reduktion kompressionsförhållanden.
Doty REF återbesökte Kučera-Gács-teorem ur den konstruktiva dimensionens synvinkel.
Every Sequence is Decompressible from a Random One
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}