Mentioned in

Asymptotic Logical Uncertainty: Uniform Coherence 2

23rd Aug 2015

0Scott Garrabrant

New Comment

1 comment, sorted by Click to highlight new comments since: Today at 9:38 PM

The two main advantages that this definition has oven the old one are that this definition allows you to disconnect the run time from the Godel number of the sentence, and this definition does not require anything to be "quickly computable." It notices patterns of all forms, but patterns that take longer to express have more time to be recognized.

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 enumeratoris 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 ϕ. If M is a sentence enumerator, we let M(t) 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(t)=⊥.Similarly, a

logical predictoris 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 ϕ and a rational number 0≤p≤1. If L is a logical predictor, we let L(ϕ,t) denote the rational number p such that when L outputs its tth # symbol, (ϕ,p) has been output between more recently than any other pair of the form (ϕ,p′). If L has not yet output any pair of the form (ϕ,p′) by time it outputs t # symbols, we say that L(ϕ,t)=12.We say that a logical predictor L is uniformly coherent if the following three axioms hold:

limt→∞L(⊥,t)=0.

If M is a sentence enumerator such that for all n the sentence M(n)→M(n+1) is provable, then limt→∞L(M(t),t) exists.

If M1, M2, and M3 are three sentence enumerators such that for all n sufficiently large, the sentence "Exactly one of M1(n), M2(n), and M3(n) is true" is provable, then limt→∞L(M1(t),t)+L(M2(t),t)+L(M3(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 ϕ, axiom 2 implies that there must be some real number PL(ϕ) such that limt→∞L(ϕ,t)=PL(ϕ).

Theorem: If L is a uniformly coherent logical predictor, then PL 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.