Asymptotic Logical Uncertainty: Uniform Coherence
EDIT: This post is out of date, the new, better definition is here.
This post is part of the Asymptotic Logical Uncertainty series. Here, I give a concrete proposal for a definition of Uniform Coherence, as mentioned here.
This is only a proposal for a definition. It may be that this definition is bad, and we would rather replace it with something else
Let be a Turing machine which on input runs for some amount of time then outputs a probability, representing the probability assigned to .
In the following definition, we fix a function (e.g. ). We say that a sequence is quickly computable if it is an increasing sequence and there exists a Turing machine which determines whether or not an input is of the form in time .
We say that is Uniformly Coherent if


If is quickly computable and for all , then exists.

If , , and are quickly computable and for all , then
Open Question 1: Does there exist a uniformly coherent logical predictor ?
Open Question 2: Does there exist a uniformly coherent logical predictor which also passes the Generalized Benford Test? (Here, we mean the generalization of the Benford Test to all irreducible patterns)
Theroem: If is uniformly coherent, then if we define , then is defined for all and is a computably approximable coherent probability assignment. (see here for definitions.)
Proof: Computable approximability is clear. For coherence, it suffices to show that is well defined, for provable , for disprovable , and .
The fact that is well defined comes from applying 2 to the sequence .
The fact that for provable , comes from applying 3 to , , and . The fact that for disprovable , comes from applying 3 to , , and , since we already know that .
The fact that comes from applying 3 to , , and then applying 3 again to , , and to get that .
Uniform Coherence is however much stronger than coherence. To see an example, consider an infinite sequence of sentences “PA is consistent on proofs of length up to .” Uniform coherence can be shown to imply that . (Each of the sentences is provable, so you can apply 3 to this sequence and a pair of sequences.)
Theorem: If we take a quickly computable sequence of mutually exclusive sentences, , then if is uniformly coherent, we have .
Proof: Let be the disjunction of all the for . Let . By 2, converges to some . Applying 3 to , and shows that converges to . Therefore, applying 3 to , , and shows that converges to 0.(Note that I assumed here that was reasonable enough that and ane also quickly computable)
This notion, by the argument you give before the final theorem, implies belief (with probability 1) in all true Π1 sentences—therefore it must disbelieve true Π2 sentences. This is quite intriguing, but likely means it’s not quite what we want.
If uniformly coherent predictors exist, their selfreferential knowledge would obey Paul Christiano’s reflection principle (which follows directly from believing true Π1 sentences).
It does not imply belief in all true Π1 sentences. If f(x) is true for all x, the probability of f(x) will go to 1 as x goes to infinity, but the probability of (¬¬)n∀xf(x) may stay bounded away from 1.
Ahh, right. Silly mistake.
So the difference in this example is that a coherent prior with approximation Pt(n) can have limtPt(ϕsn)→1 for all n, but not have limtPt(ϕst)→1; uniformly coherent must have this. To be precise, if we set Pt(ϕ):=M(┌(¬¬)tϕ┐) with M uniformly coherent, we must have this.
Correct.