The 11th International Conference on Computability, Complexity and Randomness is held in Physical Science Building 217, University of Hawaii at Manoa, January 4–8, 2016.

The conference is supported by the National Science Foundation under Grant No. 1545707.

Opening remarks

9:45 Erik Guentner (mathematics department chair)

9:46 Rod Downey (PC chair)

9:48 Bjørn Kjos-Hanssen (organizer)

The dinner is at Lulu’s at 6pm at the intersection of Kapahulu and Kalakaua. Note the change since an earlier version on the Google Form. M.K.’s reservation is for 20 people.

A special volume of Theory of Computing Systems is planned edited by Downey, Hirschfeldt, and Kjos-Hanssen.

Session chairs:

Monday

I Greg Igusa (alternate Rutger Kuyper)

II Mushfeq Khan (alternate Hayato Takahashi)

III Stephanie Blanda (alternate Uri Andrews)

IV Linda Brown Westrick (alternate Jake Pardo)

Tuesday

I Lance Fortnow (alternate Ron Peretz)

II Jeffrey Shallit (alternate Adam Case)

III Bjørn Kjos-Hanssen (alternate Rod Downey)

Wednesday

I Rod Downey (alternate Valentina Harizanov)

II Johanna Franklin (alternate Ruper Hölzl)

Thursday

I Dan Turetsky (alternate Linda Brown Westrick)

II Cristobal Rojas (alternate Wolfgang Merkle)

III Achilles Beros (alternate Joe Miller)

IV Kohtaro Tadaki (alternate Mariya Soskova)

Friday

I Satyadev Nandakumar (alternate Andrew Bridy)

II Benoit Monin (alternate Quinn Culver)

Wifi

Network: UHM

Username: conference@math.hawaii.edu

Password: will be written on the whiteboard

Speaker: Linda Brown Westrick.

Title: Seas of squares with sizes from a co-enumerable set

Abstract:

Three prominent classes of two-dimensional subshifts are the *shifts of finite type* (SFTs), the *sofic shifts*, and the *effectively closed shifts*. SFTs are obtained by forbidding finitely many local patterns. A shift is sofic if it is a *factor* of a SFT, meaning that it is the image of a SFT under a continuous shift-invariant map. And a shift is effectively closed if it is obtained by forbidding a c.e. set of local patterns.

In general, every SFT is sofic and every sofic shift is effectively closed, but the reverse implications do not hold. We would like to know what conditions on a c.e. set of forbidden patterns would guarantee that the resulting shift is not just effectively closed, but sofic. The primary purpose of this work is to expand our inventory of examples and techniques related to this question.

For each co-enumerable $S\subseteq \mathbb{N}$, consider a two-dimensional subshift $X_S$ on the alphabet $\{\text{black}, \text{white}\}$ whose elements consist of black squares of various sizes on a white background, where the side length of each square is in $S$. We show that each $X_S$ is sofic.

The entropy of a sofic shift is always less than or equal to the entropy of the SFT of which is is a factor. In two and more dimensions, it is an open question whether every sofic shift is the factor of a SFT of the same entropy. Our seas of squares do not provide a counterexample: we show that each $X_S$ is a factor of a SFT of the same entropy.

To prove our results, we build upon the self-similar Turing machine tiling construction of Durand, Romashchenko and Shen (2010). They showed that the following class of effectively closed shifts are sofic (this result was also obtained independently by Aubrun and Sablik). For each one-dimensional effectively closed subshift $W$, consider a two-dimensional shift $X_W$ whose elements consist of vertical stripes arranged so that the common row is an element of $W$. In other words, $X_W$ is obtained by “stretching” $W$ into two dimensions.

In their construction, arrays of Turing machines operating a multiple scales work together to “read” the common row, compute the forbidden words of $W$, and kill any elements whose common row contains a forbidden word. The “reading” process makes strong use of the fact that each bit of the common row is repeated infinitely often along an entire column, so the machines have many opportunities to work together to access it.

In our construction, a similar array of Turing machines “measures” the sizes of the squares in a potential element of $X_S$, computes the forbidden sizes, and kills the element if it sees a square of a forbidden size. However, an extra challenge is that each machine must measure and store the size of every single square in its vicinity, since sizes are not necessarily repeated and thus no machine can compensate for another machine overlooking a square. A high density of information must also be communicated between the machines, creating additional challenges.

Title: Degrees of the isomorphism types of structures

The Turing degree spectrum of a countable structure $A$ is the set of all Turing degrees of the isomorphic copies of $A$.

Knight proved that the degree spectrum of a structure is closed upwards, unless the structure is automorphically trivial, in which case the degree spectrum consists of a single Turing degree.

Hirschfeldt, Khoussainov, Shore, and Slinko established that for every automorphically nontrivial structure $A$, there is a symmetric irreflexive graph, a partial order, a lattice, a ring, an integral domain of arbitrary characteristic, a commutative semigroup, or a $2 $-step nilpotent group the degree spectrum of which coincides with the degree spectrum of $A$.

Jockusch and Richter defined the degree of the isomorphism type of a structure $A$ to be the least Turing degree in the degree spectrum of $A$.

Such degrees may not exist.

For example, Richter showed that linear orders and trees without computable isomorphic copies do not have degrees of their isomorphism types.

A.N. Khisamiev established the same result for abelian $p$-groups.

Richter also introduced a general combination method for building structures the isomorphism types of which have arbitrary Turing degrees.

As a corollary, she showed that there is an abelian torsion group with an arbitrary degree of its isomorphism type.

We will show how Richter’s combination method can be extended.

We will present some recent results on the degrees of the isomorphism types of structures of interest in algebra, geometry, and low-dimensional topology.

These results are obtained in collaboration with different groups of researchers.