An enumerable undecidable set with low prefix complexity: a simplified proof

Nikolay Vereshchagin

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR01-083 | 9th January 2002 00:00

Revision #1 Authors: Nikolay Vereshchagin
Accepted on: 9th January 2002 00:00
Downloads: 3405

Keywords:

KP-trivial set, prefix complexity

Abstract:

Paper:

TR01-083 | 29th October 2001 00:00

An enumerable undecidable set with low prefix complexity: a simplified proof

TR01-083 Authors: Nikolay Vereshchagin
Publication: 27th November 2001 00:33
Downloads: 3311

Keywords:

enumerable set, initial segment, Kolmogorov complexity, prefix complexity

Abstract:

We present a simplified proof of Solovay-Calude-Coles theorem
stating that there is an enumerable undecidable set with the
following property: prefix
complexity of its initial segment of length n is bounded by prefix
complexity of n (up to an additive constant).

ISSN 1433-8092 | Imprint