Cosmic Logic: a Computational Model
  We initiate a formal study of logical inferences in context of the measure
problem in cosmology or what we call cosmic logic. We describe a simple
computational model of cosmic logic suitable for analysis of, for example,
discretized cosmological systems. The construction is based on a particular
model of computation, developed by Alan Turing, with cosmic observers (CO),
cosmic measures (CM) and cosmic symmetries (CS) described by Turing machines.
CO machines always start with a blank tape and CM machines take CO's Turing
number (also known as description number or G{\" o}del number) as input and
output the corresponding probability. Similarly, CS machines take CO's Turing
number as input, but output either one if the CO machines are in the same
equivalence class or zero otherwise. We argue that CS machines are more
fundamental than CM machines and, thus, should be used as building blocks in
constructing CM machines. We prove the non-computability of a CS machine which
discriminates between two classes of CO machines: mortal that halts in finite
time and immortal that runs forever. In context of eternal inflation this
result implies that it is impossible to construct CM machines to compute
probabilities on the set of all CO machines using cut-off prescriptions. The
cut-off measures can still be used if the set is reduced to include only
machines which halt after a finite and predetermined number of steps.
