Asymptotic Logical Uncertainty: Uniform Coherence 2

post by Scott Garrabrant · 2015-08-23T20:50:54.000Z · LW · GW · 1 comments

Contents

  Open Question: Do there exist any uniformly coherent logical predictors?
  Theorem: If L is a uniformly coherent logical predictor, then PL is a coherent computably approximable prior.
None
1 comment

Part of the Asymptotic Logical Uncertainty series. A couple weeks ago, I proposed a definition of uniform coherence. I decided to change the definition so that it applies to a more general context. This post is a self contained definition of uniform coherence designed so that people can start working on the problem with no background other than this post.

Every Turing machine discussed in this post will have two infinite blank tapes to work with in addition to an infinite write only output tape. There will be a special character # for the output tape which will separate the output tape into chunks.

A sentence enumerator is a machine which outputs an infinite number of # symbols, where between each pair of adjacent # symbols is a binary string which encodes a logical sentence $\varphi$. If $M$ is a sentence enumerator, we let $M\left(t\right)$ denote the sentence written between the two most recent # symbols at time $t$. If $M$ has not yet written two # symbols by time $t$, we say that $M\left(t\right)=\perp$.

Similarly, a logical predictor is a machine which outputs an infinite number of # symbols, where between each pair of adjacent # symbols is a binary string which encodes a finite sequence of ordered pairs, with each ordered pair containing a logical sentence $\varphi$ and a rational number $0\le p\le 1$. If $L$ is a logical predictor, we let $L(\varphi ,t)$ denote the rational number $p$ such that when $L$ outputs its $t^{th}$ # symbol, $(\varphi ,p)$ has been output between more recently than any other pair of the form $(\varphi ,p^{\prime })$. If $L$ has not yet output any pair of the form $(\varphi ,p^{\prime })$ by time it outputs $t$ # symbols, we say that $L(\varphi ,t)=\frac{1}{2}$.

We say that a logical predictor $L$ is uniformly coherent if the following three axioms hold:

1. $$\underset{t\to \infty }{lim}L(\perp ,t)=0.$$

2. If $M$ is a sentence enumerator such that for all $n$ the sentence $M\left(n\right)\to M(n+1)$ is provable, then $$\underset{t\to \infty }{lim}L\left(M\right(t),t)$$ exists.

3. If $M_1$, $M_2$, and $M_3$ are three sentence enumerators such that for all $n$ sufficiently large, the sentence "Exactly one of $M_1\left(n\right)$, $M_2\left(n\right)$, and $M_3\left(n\right)$ is true" is provable, then $$\underset{t\to \infty }{lim}L\left(M_1\right(t),t)+L\left(M_2\right(t),t)+L\left(M_3\right(t),t)=1.$$

Open Question: Do there exist any uniformly coherent logical predictors?

[EDIT: This problem is no longer open]

If there are uniformly coherent logical predictors, how frequently can we make a uniformly coherent logical predictor output a # symbol?

Given a logical predictor $L$, observe that for any sentence $\varphi$, axiom 2 implies that there must be some real number $P_L\left(\varphi \right)$ such that $$\underset{t\to \infty }{lim}L(\varphi ,t)=P_L\left(\varphi \right).$$

Theorem: If $L$ is a uniformly coherent logical predictor, then $P_L$ is a coherent computably approximable prior.

The proof is similar to the proof given for the old definition, but I encourage anyone who wants to think about this problem to verify this fact for themselves as a simple exercise. You can find a definition of coherence as definition 2 here. Computable approximability just means that the probability assigned to each sentence is the limit of numbers output by a computable process.

1 comments

Comments sorted by top scores.