Computuing \(K\)-trivial sets by incomplete random sets
type: Item
instance of: scholarly article
zbMATH Open document ID: 1320.03074
author: Laurent Bienvenu
author: Adam R. Day
author: Noam Greenberg
author: Antonín Kučera
author: Joseph S. Miller
author: André Nies
author: Dan Turetsky
published in: The Bulletin of Symbolic Logic
publication date: 2014-10-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/1305.5514
Mathematics Subject Classification ID: 03D32
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 03D25
zbMATH DE Number: 6359601
zbMATH Keywords: algorithmic randomness
zbMATH Keywords: \(K\)-triviality
zbMATH Keywords: covering problem
zbMATH Keywords: Oberwolfach randomness
zbMATH Keywords: Martin-Löf-randomness
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: Chaitin complexity
MaRDI profile type: Publication
OpenAlex ID: W2154760327
arXiv ID: 1305.5514
cites work: Lowness for the class of random sets
cites work: Using random sets as oracles
cites work: Benign cost functions and lowness properties
cites work: Every sequence is reducible to a random one
cites work: Information-theoretic characterizations of recursive infinite strings
cites work: Algorithmic Randomness and Complexity
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Low upper bounds of ideals
cites work: Turing incomparability in Scott sets
cites work: On relative randomness
DOI: 10.1017/BSL.2013.3
title: Computuing \(K\)-trivial sets by incomplete random sets
review text: In algorithmic randomness, various definitions have been proposed and studied that make precise the intuitive notion of a set of a `random' or `typical' real number, Martin-Löf randomness being the paradigmatical example. Somewhat counter-intuitively, it turns out that some reals that are `random' are also `informative', in that non-computable, but computably enumerable reals can be computed from them. This motivates the question which noncomputable c.e. sets are computable from random sets. One would expect every such set to be in some sense `close to computable'. However, there are in fact random reals that solve the halting problem; once these are excluded by focusing on `incomplete' random sets, i.e. random sets that do not solve the halting problem, we get that all such reals are \(K\)-trivial, which roughly means that their initial segments carry no more information than their length in terms of prefix-free Chaitin complexity. By various results, \(K\)-trivial sets, though not necessarily computable, are indeed `close to computable'. Hence, one may now hope that this implication can be reversed, i.e. that \(K\)-trivial reals are computable from incomplete random sets, yielding a concise answer to the question which noncomputable c.e. sets are computable from random sets. It turns out that this is indeed the case in a quite strong sense: By the main theorem of the paper, there is a single incomplete Martin-Löf random set such that every \(K\)-trivial set is Turing-reducible to it. NEWLINENEWLINENEWLINEThe paper is, as the authors remark in the introduction, rather an `announcement' than a proof, giving sufficient information for an informed reader to construct a complete argument. The motivation and background of the problem are well explained, along with the various relevant results that were accumulated over time and could now finally be pieced together to lead to the main result. The paper contains virtually no proofs but points to the relevant sources. It w…
description: scientific article; zbMATH DE number 6359601