Kolmogorov complexity of initial segments of sequences and arithmetical definability
type: Item
instance of: scholarly article
title: Kolmogorov complexity of initial segments of sequences and arithmetical definability
zbMATH Open document ID: 1235.68087
author: George Barmpalias
author: C. S. Vlek
published in: Theoretical Computer Science
publication date: 2011-10-10T00:00:00Z
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 5955914
zbMATH Keywords: prefix-free Kolmogorov complexity
zbMATH Keywords: relative randomness
zbMATH Keywords: \(K\)-degrees
zbMATH Keywords: arithmetical complexity
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.06.006
OpenAlex ID: W2034673847
cites work: Elementary differences between the degrees of unsolvability and degrees of compressibility
cites work: Relative randomness and cardinality
cites work: On the gap between trivial and nontrivial initial segment prefix-free complexity
cites work: Kolmogorov Complexity and Solovay Functions
cites work: Chaitin's halting probability and the compression of strings using oracles
cites work: Randomness, lowness and degrees
cites work: On the number of infinite sequences with trivial initial segment complexity
cites work: A minimal pair of 𝐾-degrees
cites work: Algorithmic Randomness and Complexity
cites work: Q3801539
cites work: Time-Bounded Kolmogorov Complexity and Solovay Functions
cites work: Kolmogorov complexity and the Recursion Theorem
cites work: Lowness notions, measure and domination
cites work: The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
cites work: Randomness and Computability: Open Questions
cites work: On initial segment complexity and degrees of randomness
cites work: Oscillation in the initial segment complexity of random reals
cites work: Lowness properties and randomness
cites work: Q3611832
cites work: The Kolmogorov complexity of random reals
DOI: 10.1016/J.TCS.2011.06.006
description: scientific article; zbMATH DE number 5955914