Recursion-theoretic ranking and compression (Q1713478): Difference between revisions

This paper studies sets that can be compressed in an effective, but not necessarily efficient way. A set of strings \(A\) is recursively rankable if there exists a computable function \(f\) such that if the lexicogrpahical ordering of \(A\) is \(\{x_1 < x_2 < \dots \}\) then \(f(x_i)\) is the \(i\)-th string in the lexicographical ordering of the set of strings. A set of strings \(A\) is recursively computable if there exists a computable function \(f\) that maps bijectively \(A\) to the set of strings. The paper also defines the similar notions for \(f\) partially computable. The general flavor of results is that the effective compressibility and the effective rankability of a set \(A\) do not imply any bound on the position of \(A\) in the arithmetic hierarchy. For example, it is shown that every \(1\)-truth-table degree contains recursively rankable sets and recursively compressible sets.