One of the most remarkable results in finite model theory is that for any first order formula \phi the limit as n -> infinity of {M models \phi: |M| =n} / {M:|M| = n} is either 0 or 1. In other words, any formula is realized asymptotically almost surely or asymptotically almost never. This is called the 0-1 law for first order logic.

Since its discovery there have been several other 0-1 laws proved for collections of finite structures which satisfied some condition, such as being a graph, or a triangle free graph, or a partial order.

Now given any first order theory T we can look at the collection of finite subsets of models of T and we can ask if those finite subsets have a 0-1 law (i.e., does any formula asymptotically almost surely hold or asymptotically almost never hold). In the case that there is a 0-1 law the resulting theory is not necessarily the same as T.

This gives us a map 01Law from complete theories to (possibly incomplete) theories. We can then ask "How computable can the output, 01Law(T), be when the input, T, is a computable complete theory?"

In this talk we will prove that provided T is computable and 01Law(T) is complete then 01Law(T) must be computable from the halting problem. We will also show that every set computable from the halting problem is, in a strong sense, reducible to a theory of the form 01Law(T) for a computable T.

If we have time we will also discuss other properties of the 01Law operator, such as showing that for any countable ordinal \alpha there is a theory such that 01Law can be iterated \alpha many times with each iteration being a complete theory.