REPORTS > DETAIL:
Revision(s):
Revision #1 Authors: Nikolai K. Vereshchagin
Accepted on: 9th January 2002 00:00
Downloads: 435
Keywords:
Abstract:
Paper:
TR01-083 | 29th October 2001 00:00
An enumerable undecidable set with low prefix complexity: a simplified proof
TR01-083 Authors: Nikolai K. Vereshchagin
Publication: 27th November 2001 00:33
Downloads: 453
Keywords:
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).