So there is a talk about infinite-dimensional vector space being computable. But then I find it hard to understand. Apparently, dimension is infinite, so how would the operations of the space be computable?

Is it something like $\pi$ being computable, although it has infinite number of digits?

  • 4
    $\begingroup$ Elements of an $\aleph_0$-dimensional vector space written in a fixed basis are just finite sequences of field elements (considered extended with zeros to an infinite sequence), on which operations are performed coordinate-wise. The only problem is thus whether the base field (which you didn’t specify) is computable. $\endgroup$ – Emil Jeřábek Sep 9 '14 at 12:17
  • $\begingroup$ @EmilJeřábek: that's the boring case. The interesting case is when you throw in completeness, say an infinite-dimensional Hilbert space or a Banach space. $\endgroup$ – Andrej Bauer Sep 9 '14 at 20:36

Short answer

The general answer is that computability is easy for locally compact spaces, doable for separable spaces, and hard for non-separable spaces.

The short anwer for a particular example, namely $\ell^2$ is: in order to get computability on $\ell^2$ working, represent an element $x$ of $\ell^2$ by a program which accepts $n$ and gives (the list of coefficients of) a finite rational linear combination of the standard basis vectors which is within $2^{-n}$ of $x$ in the $\ell^2$ norm.

Long answer

One general way of equipping a space $X$ with computability is to choose a datatype $\mathtt{T}$ in your favorite programming language (it can be Turing machines and tapes if you're into 1950's memorabilia, otherwise I would recommend a reasonable programming language such as Haskell), and a realizability relation $\vdash_X$ on $\mathtt{T} \times X$, where $\mathtt{d} \Vdash_X x$ means "datum $\mathtt{d}$ represents (implements, realizes) the point $x \in X$". For instance, if $X$ is the space of all finite graphs, then $\mathtt{T}$ could be the datatype of adjancency matrices. If $Y$ is another space with a computability structure, then a map $f: X \to Y$ is said to be computable or realized if there is a program $\mathtt{p}$ such that $\mathtt{d} \Vdash_X x$ implies $\mathtt{p}(\mathtt{d}) \Vdash_Y f(x)$, i.e., $\mathtt{p}$ does to the representing data what $f$ does to points.

The most important principle to always keep in mind is that computability is about computability of structure, not computability of a bare set.

For instance, it makes no sense to ask "Is $\pi$ computable?" or even "Which elements of $\mathbb{R}$ are computable?" You must first make up your mind about what structure of $\mathbb{R}$ you want to consider, and then see if you can make it computable. The correct computability structure on $\mathbb{R}$ turns out to be:

  1. arithmetical operations must be computable (including the constants $0$ and $1$)
  2. the order relation $<$ must be semidecidable,
  3. there is a program which, given $d \vdash_{\mathbb{R}} x$ and $k \in \mathbb{N}$, computes a rational approximation of $x$ with precision $2^{-k}$,
  4. the limit operator $\lim$ which assigns to every rapid Cauchy sequence of reals its limit, is computable. (A sequence $(x_n)$ is rapid if $|x_n - x_m| \leq 2^{-\min(n,m)}$ for all $m, n$. The point is that we need to have a known rate of convergence, any other rate would do just as well.)

If you leave out anything, or try to add more, you will get into trouble by either having many non-equivalent computability structures on $\mathbb{R}$, or none. A datatype for representing reals for which all of the above can be implemented is $$\mathtt{nat} \to \mathtt{rational}$$ where a function $\mathtt{p}$ represents a real $x$ when, for every $n \in \mathbb{N}$, $\mathtt{p}(n)$ returns (a representatve of) a rational number $q$ such that $|x - q| \leq 2^{-n}$. (Such a function $\mathtt{p}$ may be represented by a Turing machine, or a piece of source code, or an expression in $\lambda$-calculus.)

Let us now look at an infinite dimensional space $\ell^2$. It is a real Hilbert space with a countable orthonormal basis, so the relevant structure is:

  1. vector space structure: $0$, $+$, $-$ and scalar multiplication,
  2. the scalar product: $\langle {-}, {-} \rangle$
  3. completeness: given a rapid Cauchy sequence $(x_n)$ in $\ell^2$, we can compute $\lim_n x_n$
  4. basis: for every $x \in \ell^2$ we can compute a sequence $(\lambda_n)$ of real numbers such that $x = \sum_n \lambda_n \cdot e_n$ where $$e_n = (\underbrace{0, \ldots, 0}_n, 1, 0, 0, \ldots)$$ is the canonical orthonormal basis.

Now the question is what datatype we should choose to represent $\ell^2$ so that all of the structure is computable. A simple one that works is $$\mathtt{nat} \to \mathtt{list}(\mathtt{rational}),$$ i.e, we can represent an element $x \in \ell^2$ with a function $\mathtt{p}$ that accepts a natural number and returns a finite list of rational numbers. The realizability relation is $$\mathtt{p} \Vdash_{\ell^2} x$$ is defined as follows: for every $n \in \mathbb{N}$, $p(n)$ is a list of rationals $[q_0, \ldots, q_m]$ such that $\|x - \sum_{i=0}^m q_i e_i\|_2 \leq 2^{-n}$. I leave it as an exercise to verify that with this representation we can indeed implement all of the structure of $\ell^2$, as stated above.

Further reading (sorry for blowing my own horn): A. Bauer, J. Blanck: Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions", J. UCS 16(18): 2496-2522 (2010)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.