3
$\begingroup$

An additive cost function is defined as $c: \omega\times \omega \to \mathbb{Q}_2$ such that it is recursive, monotonic (i.e. $c(x+1,y)\leq c(x,y)\leq c(x,y+1)$ and $c(x,y)=0$ whenever $x\geq y$, the intuition is: the bigger the interval, the larger the cost) and for any $x,y,z, c(x,y)+c(y,z)=c(x,z)$. Another way to look at it is each additive cost function is associated with some left-c.e real $\beta=lim_s c(0,s)$ and $\forall x\leq t \ \ c(x,t)=\beta_t-\beta_s$. A $\Delta_2^0$ $A$ is said to abey a cost function if

There exists a recursive approximation $A_s$ such that $\Sigma_{\mbox{x is the least such that $A_{t-1}(x)\neq A_t$}} c(x,t) <\infty$

In Andre Nies' paper (Calculus of Cost function)http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.2541&rep=rep1&type=pdf, the following equivalence is established:

(i) A is K-trivial. (ii) A obeys each additive cost function. (iii) A obeys $c_\Omega$ for the enumeration $\Omega_s=dom\mathbb{U}_s$. Where $\mathbb{U}$ is the universal prefix-free Turing machine.

It could be further observed that if we further require the $\Delta_2^0$ set to be recursively enumerable, then the equivalence proof does not need to use golden run method (as remarked below).

My question is: Is there a direct way of showing any recursive enumeration of a Turing complete set does not obey $c_\Omega$ or equivalently does not obey $c_\beta$ for some left-c.e. $\beta$? By saying "direct" I mean it does not need to involve golden run method since otherwise the obove equivalence plus the fact that K-trivial sets are Turing incomplete (the proof requires golden run as well!) would give a direct implication.

PS: Golden run method appeared in Nies' Lowness properties and randomness, http://www.sciencedirect.com/science/article/pii/S0001870804003469. It has relatively high proof-theoretical complexity.

$\endgroup$

1 Answer 1

2
$\begingroup$

Let $X$ be Martin-Löf random but not Oberwolfach random, and Turing incomplete. That is, $X$ is a solution to the covering problem. There is an additive cost function $c$ such that if $A$ obeys $c$, $A$ is computable from $X$. Thus nothing Turing complete can obey $c$.

Alternatively, there is a direct proof that $A$ obeying $c_\beta$ implies $A$ cannot de-randomize $\beta$. Since anything Turing complete can compute $\Omega$ (which is random), this implies nothing Turing complete can obey $c_\Omega$.

$\endgroup$
3
  • $\begingroup$ I see the first method though it still sounds like a quite involved construction to get a MLR but not OWR Turing incomplete set. For your alternative method, are you saying there is a direct proof for: If $\beta$ is a left-c.e. Martin-Löf random real and $A$ obeys $c_\beta$, then $\beta$ is also Martin-Löf random relative to $A$? I can see that by the assumption, A is K-trivial so definitely it is low for randomness. However, the implication from K-triviality to lowness for randomness seems to require golden run. Is there any other direct way of showing this? $\endgroup$
    – Jing Zhang
    Oct 28, 2013 at 14:37
  • $\begingroup$ Yes, that's what I meant. I'll edit in a proof above. $\endgroup$ Oct 28, 2013 at 15:40
  • 1
    $\begingroup$ I withdraw the claim. I tried to write it up, but I couldn't bound the measure the way I wanted. $\endgroup$ Oct 28, 2013 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.