Recent Aspects of Mass Problems:
Symbolic Dynamics and Intuitionism

Stephen G. Simpson
Department of Mathematics
Pennsylvania State University
http://www.math.psu.edu/simpson/

September 12, 2007

This note consists of an abstract and references for a talk to be given at an NSF-sponsored workshop on algorithmic randomness, at the University of Chicago, September 15-19, 2007.

Abstract

Mass Problems

A set $P\subseteq\{0,1\}^\mathbb{N}$ may be viewed as a mass problem, i.e., a decision problem with more than one solution. By definition, the solutions of $P$ are the elements of $P$. A mass problem is said to be solvable if at least one of its solutions is recursive. A mass problem $P$ is said to be Muchnik reducible to a mass problem $Q$ if for each solution of $Q$ there exists a solution of $P$ which is Turing reducible to the given solution of $Q$. A Muchnik degree is an equivalence class of mass problems under mutual Muchnik reducibility.

A set $P\subseteq\{0,1\}^\mathbb{N}$ is said to be $\Pi^0_1$ if it is effectively closed, i.e., it is the complement of the union of a recursive sequence of basic open sets. The lattice $\mathcal{P}_w$ of Muchnik degrees of mass problems associated with nonempty $\Pi^0_1$ subsets of $\{0,1\}^\mathbb{N}$ has been investigated by the speaker and others. It is known that $\mathcal{P}_w$ contains many specific, natural Muchnik degrees which are related to various topics in the foundations of mathematics. Among these topics are algorithmic randomness, reverse mathematics, almost everywhere domination, hyperarithmeticity, resource-bounded computational complexity, Kolmogorov complexity, and subrecursive hierarchies.

Symbolic Dynamics

Let $A$ be a finite set of symbols. The full two-dimensional shift on $A$ is the dynamical system consisting of the natural action of the group ${\mathbb{Z}\times\mathbb{Z}}$ on the compact space $A^{\mathbb{Z}\times\mathbb{Z}}$. A two-dimensional subshift is a nonempty closed subset of $A^{\mathbb{Z}\times\mathbb{Z}}$ which is invariant under the action of ${\mathbb{Z}\times\mathbb{Z}}$. A two-dimensional subshift is said to be of finite type if it is defined by a finite set of excluded configurations. The two-dimensional subshifts of finite type are known to form an important class of dynamical systems, with connections to mathematical physics, etc.

Clearly every two-dimensional subshift of finite type is a nonempty $\Pi^0_1$ subset of $A^{\mathbb{Z}\times\mathbb{Z}}$, hence its Muchnik degree belongs to $\mathcal{P}_w$. Conversely, we prove that every Muchnik degree in $\mathcal{P}_w$ is the Muchnik degree of a two-dimensional subshift of finite type. The proof of this result uses tilings of the plane. We present an application of this result to symbolic dynamics. Our application is stated purely in terms of two-dimensional subshifts of finite type, with no mention of Muchnik degrees.

Intuitionism

Historically, the study of mass problems originated from intuitionistic considerations. Kolmogorov 1932 proposed to view intuitionism as a ``calculus of problems.'' Muchnik 1963 introduced Muchnik degrees as a rigorous elaboration of Kolmogorov's proposal. As noted by Muchnik, the lattice of all Muchnik degrees is Brouwerian.

The question arises, is the sublattice $\mathcal{P}_w$ Brouwerian? We prove that it is not. The proof uses our adaptation of a technique of Posner and Robinson.

References

Joshua A. Cole and Stephen G. Simpson, Mass problems and hyperarithmeticity, 19 pages, 2006, submitted for publication.

Andrei N. Kolmogorov, Zur Deutung der intuitionistischen Logik, Mathematische Zeitschrift, 35, 1932, 58-65.

Albert A. Muchnik, On strong and weak reducibilities of algorithmic problems, Sibirskii Matematicheskii Zhurnal, 4, 1963, 1328-1341, in Russian.

David B. Posner and Robert W. Robinson, Degrees joining to $0'$, Journal of Symbolic Logic, 46, 1981, 714-722.

Stephen G. Simpson, Mass problems and randomness, Bulletin of Symbolic Logic, 11, 2005, 1-27.

Stephen G. Simpson, An extension of the recursively enumerable Turing degrees, Journal of the London Mathematical Society, 75, 2007, 287-297.

Stephen G. Simpson, Mass problems and almost everywhere domination, Mathematical Logic Quarterly, 53, 483-492, 2007.

Stephen G. Simpson, Medvedev degrees of 2-dimensional subshifts of finite type, 8 pages, 2007, submitted for publication.

Stephen G. Simpson, Mass problems and intuitionism, 9 pages, 2007, submitted for publication.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, 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 abstract2

The translation was initiated by Stephen G Simpson on 2007-10-17