Part of the Asymptotic Logical Uncertainty series. This post is especially dependent on the previous two posts. Here, we show that the Modified Demski Prior is Uniformly Coherent. This result came out of discussion with Benja Fallenstein, Jessica Taylor, and myself, and is primarily due to Benja.
Theorem: The Modified Demski Prior is Uniformly Coherent.
Proof: We will start with property 3 of uniform coherence. Fix a triple M1, M2, and M3 which meet the conditions for property 3. Consider the Turing machine M′ which outputs all sentences of the form "Exactly one of M1(t), M2(t), and M3(t) is true" in order. (M can generate these sentences by simulating the three Turing machines, or if we assume we have PA in our starting theory, it could just make these statements about the Turing machines.) Note that every sentence output by M4 is provable in the base theory.
As t goes to infinity, the probability that M′ is sampled by M(t) goes to 1. Further, the probability that it is sampled and accepted goes to 1. This is because the only way it can be rejected is if there exists a contradiction in the sentences output by the Turing machines sampled earlier. For every list of Turing machines output earlier, there is a fixed value t after which M(t) will accept M′ if that list is the list of machines sampled before M′. For any ε we can take t large enough that this is true for the list of sentences sampled with probability 1−ε.
Therefore, as t goes to infinity, the probability that M(t) outputs the sentence "Exactly one of M1(t), M2(t), and M3(t) is true" goes to 1. The probability that M(t) later individually outputs the six Turing machines which give the single sentences M1(t), ¬M1(t), M2(t), ¬M2(t), M3(t), and ¬M3(t), consecutively in that order also goes to 1 as t goes to infinity, since the complexity of the Turing machine which outputs those sentences is only a constant more than the complexity it takes to output the integer t, which is on the order of logt, and we sample 2t Turing machines. Since K notices all propositional contradictions and must accept either Mi(t) or ¬Mi(t), the sum of the probabilities that M accepts M1(t), M2(t), and M3(t) must go to one. Therefore, limt→∞L(M1(t),t)+L(M2(t),t)+L(M3(t),t)=1.
The fact that the algorithm satisfies property 1 is trivial, so all that remains is to show that it satisfies property 2. Consider a Turing machine M′ which satisfies the conditions of property 2. Consider the infinite class of Turing machines M′i (i=∞,0,1,…) which outputs the same sentences as M′, but negates the first i sentences output. Note that in any complete theory sampled by the oracle version of the modified Demski prior, exactly one of these Turing machines only outputs true sentences. Let Ei be the event that M′i outputs only true sentences. Note that for each event Ei, the probability that M′i is sampled and accepted in M(t) goes to 1 as t goes to infinity. (Here, we are taking the execution path of M(t) which comes from a random infinite order of Turing machines which satisfies Ei.) Therefore, conditioning on each each Ei, i<∞, the probability that M(t) outputs M′(t) converges to 0, while conditioning on E∞, the probability that M(t) outputs M′(t) converges to 1. Therefore, since the probabilities conditioned on each event are all bounded (between 0 and 1), and each one converges, the infinite weighted average also converges, so the probability that M(t) outputs M′(t) converges. In fact, it converges to the probability of ¬E∞. Since the probabilities that M(t) accept the sentences M′(t) converge, the probability L(M′(t),t) also converges.□
Part of the Asymptotic Logical Uncertainty series. This post is especially dependent on the previous two posts. Here, we show that the Modified Demski Prior is Uniformly Coherent. This result came out of discussion with Benja Fallenstein, Jessica Taylor, and myself, and is primarily due to Benja.
Theorem: The Modified Demski Prior is Uniformly Coherent.
Proof: We will start with property 3 of uniform coherence. Fix a triple M1, M2, and M3 which meet the conditions for property 3. Consider the Turing machine M′ which outputs all sentences of the form "Exactly one of M1(t), M2(t), and M3(t) is true" in order. (M can generate these sentences by simulating the three Turing machines, or if we assume we have PA in our starting theory, it could just make these statements about the Turing machines.) Note that every sentence output by M4 is provable in the base theory.
As t goes to infinity, the probability that M′ is sampled by M(t) goes to 1. Further, the probability that it is sampled and accepted goes to 1. This is because the only way it can be rejected is if there exists a contradiction in the sentences output by the Turing machines sampled earlier. For every list of Turing machines output earlier, there is a fixed value t after which M(t) will accept M′ if that list is the list of machines sampled before M′. For any ε we can take t large enough that this is true for the list of sentences sampled with probability 1−ε.
Therefore, as t goes to infinity, the probability that M(t) outputs the sentence "Exactly one of M1(t), M2(t), and M3(t) is true" goes to 1. The probability that M(t) later individually outputs the six Turing machines which give the single sentences M1(t), ¬M1(t), M2(t), ¬M2(t), M3(t), and ¬M3(t), consecutively in that order also goes to 1 as t goes to infinity, since the complexity of the Turing machine which outputs those sentences is only a constant more than the complexity it takes to output the integer t, which is on the order of logt, and we sample 2t Turing machines. Since K notices all propositional contradictions and must accept either Mi(t) or ¬Mi(t), the sum of the probabilities that M accepts M1(t), M2(t), and M3(t) must go to one. Therefore, limt→∞L(M1(t),t)+L(M2(t),t)+L(M3(t),t)=1.
The fact that the algorithm satisfies property 1 is trivial, so all that remains is to show that it satisfies property 2. Consider a Turing machine M′ which satisfies the conditions of property 2. Consider the infinite class of Turing machines M′i (i=∞,0,1,…) which outputs the same sentences as M′, but negates the first i sentences output. Note that in any complete theory sampled by the oracle version of the modified Demski prior, exactly one of these Turing machines only outputs true sentences. Let Ei be the event that M′i outputs only true sentences. Note that for each event Ei, the probability that M′i is sampled and accepted in M(t) goes to 1 as t goes to infinity. (Here, we are taking the execution path of M(t) which comes from a random infinite order of Turing machines which satisfies Ei.) Therefore, conditioning on each each Ei, i<∞, the probability that M(t) outputs M′(t) converges to 0, while conditioning on E∞, the probability that M(t) outputs M′(t) converges to 1. Therefore, since the probabilities conditioned on each event are all bounded (between 0 and 1), and each one converges, the infinite weighted average also converges, so the probability that M(t) outputs M′(t) converges. In fact, it converges to the probability of ¬E∞. Since the probabilities that M(t) accept the sentences M′(t) converge, the probability L(M′(t),t) also converges.□