Article ID Journal Published Year Pages File Type
427706 Information Processing Letters 2012 4 Pages PDF
Abstract

We construct a K  -trivial c.e. set which is not jump traceable at any order in o(logx).

► There is a K  -trivial set which is not jump traceable at any o(logn) order. ► The construction applies to all orders satisfying a certain summability property. ► The construction relies on the additive cost function characterization of K-triviality.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,