This is the abstract of my 15-minute talk at a special session on Logic and Dynamical Systems, sponsored by the American Mathematical Society (AMS) and the Association for Symbolic Logic (ASL). The session is part of the Joint Mathematics Meetings, January 5-8, 2009 in Washington, DC.
Let be a finite set of symbols. The -dimensional shift space on is with shift operators and given by and . A -dimensional subshift is a nonempty, closed subset of which is invariant under and . A -dimensional subshift is said to be of finite type if it is defined by a finite set of excluded finite configurations of symbols. We regard real numbers and points of as Turing oracles. If and are sets of Turing oracles, we say that is Muchnik reducible to if each can be used to compute some . The Muchnik degree of is the equivalence class of under mutual Muchnik reducibility. We prove that the Muchnik degrees of -dimensional subshifts of finite type are the same as the Muchnik degrees of nonempty, effectively closed sets of real numbers. We then apply known results about such Muchnik degrees to obtain an infinite family of -dimensional subshifts of finite type which are, in a certain strong sense, mutually independent. Our application is stated purely in terms of symbolic dynamics, with no mention of Muchnik reducibility.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 abstract
The translation was initiated by Stephen G Simpson on 2008-12-17