Title: Recursion theory and symbolic dynamics Speaker: Steve Simpson Abstract: There are many connections between d-dimensional symbolic dynamics and Turing's theory of computability and unsolvability. Given a d-dimensional system of finite type, consider the associated *orbit problem*, i.e., the problem of finding at least one orbit of the system. For d = 1 it is well known that the orbit problem is algorithmically solvable, because one can find a periodic orbit. Meyers in 1974 constructed a 2-dimensional system of finite type for which the orbit problem is algorithmically unsolvable, i.e., no orbit of the system is computable in the sense of Turing. In a paper to appear in Ergodic Theory and Dynamical Systems, I improved Meyers's result by constructing 2-dimensional systems of finite type for which the orbit problem has any desired degree of unsolvability. In another direction, recall that the Kolmogorov complexity of a finite mathematical object tau may be roughly described as the size, measured in bits, of the smallest Turing machine program which describes tau. In a recent paper to appear in Theory of Computing Systems, I obtained a sharp characterization of the topological entropy of a d-dimensional symbolic system X in terms of the Kolmogorov complexity of the finite configurations of symbols which occur in X. I also showed that the topological entropy of X coincides with the Hausdorff dimension of X with respect to the standard metric.