On the gap between trivial and nontrivial initial segment prefix-free complexity
type: Item
instance of: scholarly article
title: On the gap between trivial and nontrivial initial segment prefix-free complexity
zbMATH Open document ID: 1261.68075
author: Martijn Baartse
author: George Barmpalias
published in: Theory of Computing Systems
publication date: 2013-04-15T00:00:00Z
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 6153895
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: initial segment prefix-free complexity
zbMATH Keywords: \(K\)-triviality
zbMATH Keywords: low for \(\varOmega \)
MaRDI profile type: Publication
full work available at URL: s00224-012-9400-9
OpenAlex ID: W2040912355
cites work: Compactness arguments with effectively closed sets for the study of relative randomness
cites work: Elementary differences between the degrees of unsolvability and degrees of compressibility
cites work: Relative randomness and cardinality
cites work: \(\Pi_1^0 \) classes, LR degrees and Turing degrees
cites work: Q3113710
cites work: On the number of infinite sequences with trivial initial segment complexity
cites work: Kolmogorov complexity of initial segments of sequences and arithmetical definability
cites work: Information-theoretic characterizations of recursive infinite strings
cites work: A minimal pair of 𝐾-degrees
cites work: Turing degrees of reals of positive effective packing dimension
cites work: Algorithmic Randomness and Complexity
cites work: RELATIVIZING CHAITIN'S HALTING PROBABILITY
cites work: Using random sets as oracles
cites work: Turing incomparability in Scott sets
cites work: The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
cites work: Q3611832
cites work: Measures and their random reals
DOI: 10.1007/S00224-012-9400-9
description: scientific article; zbMATH DE number 6153895