Klaus Weihrauch

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of ${\rm TIME}$ as the maximum of a generally infinite ... more >>>

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

The ``analyst's traveling salesman theorem'' of geometric

measure theory characterizes those subsets of Euclidean

space that are contained in curves of finite length.

This result, proven for the plane by Jones (1990) and

extended to higher-dimensional Euclidean spaces by

Okikiolu (1991), says that a bounded set $K$ is contained

more >>>

Jack H. Lutz, Neil Lutz

This paper proves that there is, in every direction in Euclidean space, a line that misses every computably random point. Our proof of this fact shows that a famous set constructed by Besicovitch in 1964 has computable measure 0.

more >>>Adam Case, Jack H. Lutz

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory ... more >>>