Personal tools
You are here: Home 2000 The computational dimension of a topological space

The computational dimension of a topological space

Hideki Tsuiki University of Kyoto 3pm, Tuesday 28 November 2000 Room 2511, JCMB, King's Buildings

When a topological space $X$ can be embedded into the space $\Sigma_{\bot,n}^\omega$ of $n\bot$-sequences of $\Sigma$, which are infinite sequences of $\Sigma$ in which at most $n$ undefined cells are allowed to exist, then we can define the corresponding computational notion over $X$ because a machine with $n+1$ heads on each tape can input/output sequences in $\Sigma_{\bot,n}^\omega$.

This means that the least number $n$ such that $X$ can be topologically embedded into $\Sigma_{\bot,n}^\omega$ serves as a degree of complexity of the space. We show that this number, which we call the computational dimension of the space, is equal to the topological dimension for separable metric spaces. As a corollary, the 2-dimensional Euclidean space $R^2$ can be embedded in $\{0,1\}^\omega_{\bot,2}$ but not in $\{0,1\}^\omega_{\bot,1}$ for any character set $\Sigma$, and infinite dimensional spaces like the set of closed/open/compact subsets of $R^n$ and the set of continuous functions from $R^n$ to $R^m$ can be embedded in $\sigbot$ but not in $\Sigma_{\bot,n}^\omega$ for any $n$.