Asymptotic Logical Uncertainty: The Modified Demski Prior is Uniformly Coherent

by Scott Garrabrant2 min read23rd Aug 2015No comments

4

Personal Blog

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 , , and which meet the conditions for property 3. Consider the Turing machine which outputs all sentences of the form "Exactly one of , , and is true" in order. ( 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 is provable in the base theory.

As goes to infinity, the probability that is sampled by 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 after which will accept if that list is the list of machines sampled before . For any we can take large enough that this is true for the list of sentences sampled with probability .

Therefore, as goes to infinity, the probability that outputs the sentence "Exactly one of , , and is true" goes to 1. The probability that later individually outputs the six Turing machines which give the single sentences , , , , , and , consecutively in that order also goes to 1 as 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 , which is on the order of , and we sample Turing machines. Since notices all propositional contradictions and must accept either or , the sum of the probabilities that accepts , , and must go to one. Therefore,

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 which satisfies the conditions of property 2. Consider the infinite class of Turing machines () which outputs the same sentences as , but negates the first 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 be the event that outputs only true sentences. Note that for each event , the probability that is sampled and accepted in goes to 1 as goes to infinity. (Here, we are taking the execution path of which comes from a random infinite order of Turing machines which satisfies .) Therefore, conditioning on each each , , the probability that outputs converges to , while conditioning on , the probability that outputs converges to . 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 outputs converges. In fact, it converges to the probability of . Since the probabilities that accept the sentences converge, the probability also converges.

Personal Blog

4

New Comment