4
$\begingroup$

The usual listing $\{\varphi_e: e\in\omega\}$ of partial computable functions has a number of nice properties - the padding lemma, the recursion theorem, etc. Any other numbering which we can "effectively translate" to and from this numbering also has these properties, and such numberings are called acceptable numberings.

However, there are also computable numberings which are terrible. The most famous examples are Friedberg numberings: these are computable enumerations of computable partial functions such that each function appears exactly once. They violate basically everything.

Here's another kind of weird numbering (motivation below). Conflate a total computable $f$ with the numbering $\{\varphi_{f(e)}: e\in\omega\}$ it produces. Then say $f$ is prescient if for all $a$ there are infinitely many $s$ which are "strongly true stages" for $a$: $$\forall t<s, b<a[\varphi_{f(t)}(b)\upharpoonright s\cong \varphi_{f(t)}(b)].$$ That is, any computation with $f$-index coming before $s$ on any input less than $a$ halts iff it halts by stage $s$.

It's not hard to show that no acceptable numbering is prescient. However, it's also not hard to show that there are acceptable numberings, via a finite injury construction.

Prescient numberings arose in the context of a project I'm working on in $\alpha$-recursion theory: if $\kappa<\alpha$ is a cardinal, then every Turing machine with index $<\kappa$ on input $<\kappa$ halts by stage $\kappa$ or not at all. Such "strongly true stages" don't exist in $\omega$-computability theory in any way; however, numberings of the above type are weak approximations to this property which we can achieve.


OK, so what?

Well, consider for example the Friedberg-Muchnik argument. It begins by fixing an enumeration of the partial computable functions, and proceeds from there. If you change the enumeration, you change the c.e. sets FM builds, and in fact as long as your enumeration is acceptable we can prove some basic facts about these sets (e.g. that they are low and cup to $0'$).

But the argument works even if we use a non-acceptable numbering! As long as we get every partial computable function in our list, and our list is computable, we can use it to get an incomparable pair of c.e. sets.

And indeed, every priority argument I'm aware of shares this feature: that, although the details depend on the numbering used, the argument itself works for any effective numbering. (In some cases you need to tweak the argument a little bit - e.g. have infinitely many requirements corresponding to each index $e$ in your numbering, in case your numbering doesn't satisfy the padding lemma - but I've never seen these tweaks be nontrivial.)

Now, some of the complexity of specific priority arguments turns on the need to prove various essentially combinatorial results about true (or true enough) stages in various senses. But we've seen above an example indicating that - if we are willing to use terrible numberings - we can get artificially nice "true stage"-ish behavior. And of course it's not the only one - we can cook up weird numberings with interesting truth properties ad infinitum.

My question is:

Are specific kinds of non-acceptable numberings (such as, but not limited to, the examples above), by virtue of having nice combinatorial properties at the cost of acceptability, ever useful in simplifying priority arguments?

Basically, is there any reason to cook up a weird numbering as a step in proving (or simplifying the proofs of) a theorem about c.e. sets? My instinct is "no," that the fun properties you can cram into a numbering are not enough for the subtle arguments needed, but I'd love for the answer to be "yes".

$\endgroup$
1
  • $\begingroup$ Intuitively, the "meat" of the proof needs to be somewhere. It can be in a (complicated) construction based on an acceptable numbering or it can be in a (simple) construction based on a non-acceptable numbering. But I'm doubtful that the inherent "complexity" of a proof can be reduced by changing the numbering, unless doing so finds a new "proof" of the fact. $\endgroup$ Sep 4, 2017 at 13:32

0

Your Answer

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

Browse other questions tagged or ask your own question.