Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPUTABLE ANALYSIS:
Reports tagged with computable analysis:
TR02-014 | 10th December 2001
Klaus Weihrauch

#### Computational Complexity on Computable Metric Spaces

Revisions: 1

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 >>>

TR05-157 | 10th December 2005
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

#### Points on Computable Curves

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 >>>

TR14-015 | 24th January 2014
Jack H. Lutz, Neil Lutz

#### Lines Missing Every Random Point

Revisions: 1

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 >>>

TR14-133 | 15th October 2014
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 >>>