Category Archives: Computable Metric Spaces

Article on Dense Computability Structures

On December 9 2020 the joint work with professor Zvonko Iljazović on dense computability structures was finally reviewed and accepted for publication in Journal of Complexity. The link to the article can be found here.

This work was done prior to my employment at Amazon.

Two questions related to computability structures on the unit square

The following questions were proposed to me by professor Zvonko Iljazović.

Let $I = [0,1]$ . We define the metric $d_\infty$ be the metric defined as

$d_\infty((x_1,x_2), (y_1,y_2)) = \max (|x_1 - y_1|, |x_2 - y_2|).$

for all $(x_1,x_2), (y_1,y_2) \in I^2$ . Let $\mathcal{M} = (I^2, d_\infty)$ .

Let $a = (0,0)$ and $b = (0,1)$ . Suppose $(x_i)$ is a sequence in $\mathcal{M}$ such that the sequences $d(x_i, a)$ and $d(x_i,b)$ are computable sequences $\mathbb{N} \rightarrow \mathbb{R}$ ? Does the sequence $(x_i)$ need to be computable in the sense that its components are computable sequences $\mathbb{N} \rightarrow \mathbb{R}$ ?

Rendered by QuickLaTeX.com

Let $w = (1, \gamma)$ where $0 < \gamma < 1$ is an incomputable real. Then $d_\infty(x_i, a) = d_\infty(x_i, b)=1$ however, $(x_i)$ is not a computable sequence.

Now the second question. Let $a=(0,0)$ , $b=(0,1)$ and $c=(1,0)$ . Let $(x_i)$ be a sequence such that $d_\infty(x_i,a)$ , $d_\infty(x_i,b)$ and $d_\infty(x_i,c)$ are computable sequences $\mathbb{N} \rightarrow \mathbb{R}$ . Does the sequence $(x_i)$ need to be computable?

The answer is yes. The proof is available in our upcoming publication "Dense Computability Structures".

Proposition:
The metric space $\mathcal{M}$ has at least two maximal computability structures in which points $a=(0,0)$ and $b=(0,1)$ are computable.

Proof:
Let $(q_j)$ be a computable sequence in $\mathbb{R}^2$ such that $\mathrm{Im}\ q = \mathbb{Q}^2 \cap \mathcal{M}$ . Let $S_q$ be a computability structure induced by $q$ . Since $S_q$ is separable, it is also maximal.

Let $c = (1,\gamma)$ where $\gamma \in \langle 0,1 \rangle$ is an incomputable real. Then the finite sequence $(a,b,c)$ has the property $d_\infty(a,b) = d_\infty(a,c) = d_\infty(b,c) = 1$ hence by definition $(a,b,c)$ is an effective finite sequence.
Therefore,

$T = \{(a,a,a,\dots), (b,b,b,\dots), (c,c,c,\dots)\}$

is a computability structure and there exists a maximal computability structure $M$ such that $T \subseteq M$ and $a,b,c$ are computable points in $M$ .

On the other hand, the point $c$ is not computable in $S_q$ since that would contradict the fact that $w$ is a non-computable real. This is equivalent to the fact that $(c,c,c,\dots) \not \in S_q$ . Therefore, $M \not = S_q$ . From this we conclude that $M$ and $S_q$ are two maximal computability structures on $\mathcal{M}$ in which points $a$ and $b$ are computable.

Finite metric bases and computability structures

Introduction

In July 2018 professor Zvonko Iljazović and myself have attended the CCA 2018 conference and presented our joint work titled "Effective compactness and uniqueness of maximal computability structures". The original presentation can be found here.

Computability structures

In the following I will mention the elements of the theory of computability structures needed to state our main result. These notions are already well known, the main contributing articles for this theory that were used for our work are listed in the references.

Let $(X,d)$ be a metric space and $(x_i)$ a sequence in $X$ . We say $(x_i)$ is an effective sequence in $(X, d)$ if the function $\mathbb{N}^2 \rightarrow \mathbb{R}$

$(i,j) \mapsto d(x_i, x_j)$

is recursive.

A finite sequence $x_0,\dots,x_n$ is an effective finite sequence if $d(x_i, x_j)$ is a recursive real number for each $i,j \in \{0, \dots, n\}$ .

If $(x_i)$ and $(y_j)$ are sequences in $X$ , we say $((x_i), (y_j))$ is an effective pair in $(X,d)$ and write $(x_i) \diamond (y_j)$ if the function $\mathbb{N}^2 \rightarrow \mathbb{R}$ ,

$(i,j) \mapsto d(x_i, y_j)$

is recursive.

Let $(X,d)$ be a metric space and $(x_i)$ a sequence in $X$ . A sequence $(y_i)$ is computable w.r.t $(x_i)$ in $(X,d)$ iff there exists a computable $F:\mathbb{N}^2\rightarrow \mathbb{N}$ such that

$d(y_i, x_{F(i, k)}) < 2^{-k}$

for all $i,k \in \mathbb{N}$ . We write $(x_i) \preceq (y_j)$ .

Let $(X, d)$ be a metric space. A set $\mathcal{S} \subseteq X^\mathbb{N}$ is a computability structure on $(X,d)$ if the following holds:

$(x_i), (y_j) \in \mathcal{S}$ , then $(x_i) \diamond (y_j)$
if $(x_i) \in \mathcal{S}$ and $(y_j) \preceq (x_i)$ , then $(y_j) \in \mathcal{S}$

We say $x$ is a computable point in $\mathcal{S}$ iff $(x,x,\dots) \in \mathcal{S}$ .

A computability structure $\mathcal{S}$ such that there exists a dense sequence $\alpha \in \mathcal{S}$ is called separable.

We say $\mathcal{S}$ is a maximal computability structure on $(X, d)$ if there exists no computability structure $\mathcal{T}$ such that $\mathcal{S} \subseteq \mathcal{T}$ and $\mathcal{S} \not = \mathcal{T}$ .

The main question

The main question we are asking and trying to answer is the following:

Question:Let $(X,d)$ be a metric space. Let $a_0,\dots,a_k \in X$ . Let $\mathcal{M}$ be a maximal computability structure in which $a_0,\dots,a_k$ are computable. Under which conditions is such $\mathcal{M}$ unique?

A known result for sub-spaces of the Euclidean space

Let $V$ be a real vector space. Let $a_0,\dots,a_k$ be vectors in $V$ . We say that $a_0,\dots, a_k$ are geometrically independent points if $a_1 - a_0, \dots, a_k - a_0$ are linearly independent vectors.

Let $X \subseteq V$ . The largest $k \in \mathbb{N}$ such that that there exist geometrically independent points $a_0,\dots, a_k \in X$ we call the affine dimension of $X$ , and write $\mathrm{dim}\ X = k$ .

The following result from [1] already answers the main question in the case where $(X,d)$ is a sub-space of the Euclidean space.

Theorem: Let $X \subseteq \mathbb{R}^n$ , $k = \mathrm{dim}\ X$ and $k \geq 1$ . If $a_0,\dots,a_{k-1}$ is a geometrically independent effective finite sequence on $X$ then there exists an unique maximal computability structure on $X$ in which $a_0,\dots,a_{k-1}$ are computable points.

Main result for more general metric spaces

We wanted to introduce for general metric spaces a notion which will be a sort of replacement to the notion of geometric independence.

In the original presentation we used the term nice sequence. It turns out that this notion is a special case of the well-known notion of a metric base.

Let $(X, d)$ be a metric space. A subset $S \subseteq X$ is called a metric base for $(X,d)$ iff for all $x,y \in X$ the following implication holds: $d(x,s) = d(y,s)$ for all $s \in S$ implies $x=y$ .

A metric space $(X,d)$ is said to be effectively compact if there exist an effective separating sequence $\alpha$ in $(X,d)$ and a computable function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that

$X=B(\alpha _{0} ,2^{-k})\cup \dots \cup B(\alpha _{f(k)},2^{-k})$

for each $k\in \mathbb{N}$ . It is known that if $(X,d)$ is effectively compact, then for each effective separating sequence $\alpha$ in $(X,d)$ there exists such a computable function $f$ .

A metric base is exactly the notion we needed to obtain the following result, at least for effectively compact metric spaces.

Theorem: Let $(X,d)$ be an effectively compact metric space. Suppose $a_{0} ,\dots ,a_{n}$ is a metric base in $(X,d)$ and suppose that there exists a separable computability structure $\mathcal{S}$ on $(X,d)$ in which $a_{0} ,\dots ,a_{n}$ are computable points. Then $\mathcal{S}$ is a unique maximal computability structure on $(X,d)$ in which $a_{0} ,\dots ,a_{n}$ are computable points.

In fact, an even more general form of the theorem holds: the assumption of effective compactness of the space $(X,d)$ can be replaced with the assumption that $(X,d)$ has compact closed balls and there exists $\alpha$ such that the computable metric space $(X,d,\alpha)$ has the effective covering property.

Proofs will be presented in our future up-coming publication.

References

Zvonko Iljazović. Isometries and Computability Structures. Journal of Universal Computer Science, 16(18):2569--2596, 2010.
Zvonko Iljazović and Lucija Validžić. Maximal computability structures. Bulletin of Symbolic Logic, 22(4):445--468, 2016.
Alexander Melnikov. Computably isometric spaces. Journal of Symbolic Logic, 78:1055--1085, 2013.
Marian Pour-El and Ian Richards. Computability in Analysis and Physics. Springer-Verlag, Berlin-Heielberg-New York, 1989.
Klaus Weihrauch. Computable Analysis. Springer, Berlin, 2000.
M. Yasugi, T. Mori and Y. Tsujji. Effective properties of sets and functions in metric spaces with computability structure. Theoretical Computer Science}, 219:467--486, 1999.
M. Yasugi, T. Mori and Y. Tsujji. Computability structures on metric spaces. Combinatorics, Complexity and Logic Proc. DMTCS96 (D.S.~Bridges et al), Springer, Berlin}, 351--362, 1996.