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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.

Improve this answer
$\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
    Commented Oct 28, 2013 at 14:37
  • $\begingroup$ Yes, that's what I meant. I'll edit in a proof above. $\endgroup$
    – Dan Turetsky
    Commented 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$
    – Dan Turetsky
    Commented Oct 28, 2013 at 16:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .