ECCC-Report TR01-083https://eccc.weizmann.ac.il/report/2001/083Comments and Revisions published for TR01-083en-usWed, 09 Jan 2002 00:00:00 +0200
Revision 1
| |
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2001/083#revision1Wed, 09 Jan 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2001/083#revision1
Paper TR01-083
| An enumerable undecidable set with low prefix complexity: a simplified proof |
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2001/083We 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).
Tue, 27 Nov 2001 00:33:22 +0200https://eccc.weizmann.ac.il/report/2001/083