What are computable metric spaces?
We can generalize the notions of computability over the reals and in the euclidean space to metric spaces. A computable metric space is a triple 
where 
is a metric space and 
is a sequence in 
such that its image is dense in and the function 
defined as 
is computable. For example, a definition of computable point is a generalization of the computable real: A point 
is computable in if there exists a computable function 
such that 
for every 
. Similarly, we can define a computable sequence of points in and functions between metric spaces that are computable,... but for subsets of it is not the same as definition of computability in 
but it borrows the definitions from classical recursion theory. First we fix some computable enumeration of rational balls in for example let 
be a fixed such enumeration. Then for a set 
we say that 
is recursively enumerable 
is recursively enumerable i.e. there exists a computable function such that 
. A subset is co-recursively enumerable if we have an algorithm that covers the complement of with rational balls. In other words, is co-recursively computable iff there exists a recursively enumerable subset 
of 
such that 
. A subset is computable iff is recursively computable and co-recursively computable.
We can of course generalize further and define computable topological spaces but I shall not go further into that. That is a topic for another post. Note that as we generalize more and more there are pathological spaces that do not have nice computability properties and must be more and more careful when dealing with computability.
Copyright © 2014, Konrad Burnik
