{"id":228,"date":"2014-08-31T23:01:02","date_gmt":"2014-08-31T23:01:02","guid":{"rendered":"http:\/\/konrad.burnik.org\/wordpress\/?p=228"},"modified":"2022-01-31T14:49:13","modified_gmt":"2022-01-31T14:49:13","slug":"computable-metric-spaces","status":"publish","type":"post","link":"https:\/\/konrad.burnik.org\/wordpress\/computable-metric-spaces\/","title":{"rendered":"Computable metric spaces in a nutshell"},"content":{"rendered":"

What are computable metric spaces?<\/strong><\/p>\n

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 \"(X,d,\alpha)\" where \"(X,d)\" is a metric space and \"\alpha\" is a sequence in \"X\" such that its image is dense in \"X\" and the function \"\mathbb{N}^2 \rightarrow \mathbb{R}\" defined as \"(i,j) \mapsto d(\alpha_i, \alpha_j),\ \forall i,j\in\mathbb{N}\" \u00a0is computable. For example, a definition of computable point is a generalization of the computable real: A point \"x \in X\" is computable in \u00a0\"(X,d,\alpha)\" if there exists a computable function \"f:\mathbb{N} \rightarrow \mathbb{N}\" such that \"d(\alpha_{f(k)}, x) < 2^{-k}\" \u00a0for every \"k \in \mathbb{N}\". Similarly, we can define \u00a0a computable sequence of points in \"X\" and functions between metric spaces that are computable,... but for subsets of \"X\" it is not the same as definition of computability in \"\mathbb{R}^n\" but it borrows the definitions from classical recursion theory. First we fix some computable enumeration of rational balls in \"X\" for example let \u00a0\"(I_i)\" be a fixed such enumeration. Then for a set \"S \subseteq X\" we say that \"S\" is recursively enumerable \"T = \{i \in \mathbb{N} | S \cap I_i \not = \emptyset\}\" is recursively enumerable i.e. there exists a computable function \"f:\mathbb{N} \rightarrow \mathbb{N}\" such that \"f(\mathbb{N}) = T\". A subset \"S\" is co-recursively enumerable if we have an algorithm that covers the complement of \"S\" with rational balls. In other words, \"S\" is co-recursively computable iff there exists a recursively enumerable subset \"A\" of \"\mathbb{N}\" such that \"X \setminus S = \bigcup_{i \in A} I_i\". A subset \"S\" is computable iff \"S\" is recursively computable and co-recursively computable.<\/span>

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.<\/span><\/p>\n

Copyright \u00a9 2014, Konrad Burnik<\/p>\n

0<\/span><\/a><\/div> <\/div>
<\/div><\/div>
<\/div>","protected":false},"excerpt":{"rendered":"

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 \u00a0is computable. For […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"_s2mail":"yes","footnotes":""},"categories":[5],"tags":[],"class_list":["post-228","post","type-post","status-publish","format-standard","hentry","category-computable-metric-spaces"],"_links":{"self":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/228","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/comments?post=228"}],"version-history":[{"count":4,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/228\/revisions"}],"predecessor-version":[{"id":1212,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/228\/revisions\/1212"}],"wp:attachment":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/media?parent=228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/categories?post=228"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/tags?post=228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}