Coherence of reducibilities with randomness notions
type: Item
instance of: scholarly article
title: Coherence of reducibilities with randomness notions
zbMATH Open document ID: 1436.03228
author: Kenshi Miyabe
published in: Theory of Computing Systems
publication date: 2018-10-05T00:00:00Z
Mathematics Subject Classification ID: 03D32
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 6948124
zbMATH Keywords: Schnorr reducibility
zbMATH Keywords: van Lambalgen reducibility
zbMATH Keywords: decidable machine
MaRDI profile type: Publication
full work available at URL: s00224-017-9752-2
OpenAlex ID: W2594327249
cites work: Algorithmic randomness and measures of complexity
cites work: Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs
cites work: Kolmogorov Complexity and Solovay Functions
cites work: Solovay functions and their applications in algorithmic randomness
cites work: Reconciling Data Compression and Kolmogorov Complexity
cites work: Limit complexities revisited
cites work: Effectively approximating measurable sets by open sets
cites work: Schnorr randomness
cites work: Algorithmic Randomness and Complexity
cites work: On Kurtz randomness
cites work: Schnorr triviality and genericity
cites work: Schnorr trivial sets and truth-table reducibility
cites work: Every 2-random real is Kolmogorov random
cites work: The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
cites work: On initial segment complexity and degrees of randomness
cites work: Schnorr triviality and its equivalent notions
cites work: Reducibilities relating to Schnorr randomness
cites work: Q3611832
cites work: Randomness, relativization and Turing degrees
cites work: Von Mises' definition of random sequences reconsidered
DOI: 10.1007/S00224-017-9752-2
description: scientific article; zbMATH DE number 6948124