{"id":191,"date":"2014-08-29T21:32:14","date_gmt":"2014-08-29T21:32:14","guid":{"rendered":"http:\/\/konrad.burnik.org\/wordpress\/?p=191"},"modified":"2025-02-14T21:17:49","modified_gmt":"2025-02-14T21:17:49","slug":"introduction-to-computable-analysis-part-i","status":"publish","type":"post","link":"https:\/\/konrad.burnik.org\/wordpress\/introduction-to-computable-analysis-part-i\/","title":{"rendered":"Introduction to computable analysis (Part 1\/2)"},"content":{"rendered":"

What is Computable analysis anyway?<\/strong><\/p>\n

Roger Penrose in his book \"The emperors new Mind\" asked an interesting question regarding the Mandelbrot set: \"Is the Mandelbrot set recursive?\" The term \"recursive\" is an old name for \"computable\" and has nothing to do with recursion in programming.<\/p>\n

\"The<\/a>

The Mandelbrot Set (zoomed in)<\/p><\/div>\n

Classical computability theory (also known as recursion theory) is a branch of mathematical logic that deals with studying what functions \"\mathbb{N}\rightarrow \mathbb{N}\" are computable.\u00a0<\/span>Computable analysis is in some sense an extension of this theory.\u00a0It is a branch of mathematics that applies computability theory to problems in mathematical analysis. It is concerned with questions of effectivity in analysis and its main goal is to find what parts of analysis can be described by an algorithmic procedure, one of the basic questions being what functions \"f:\mathbb{R}\rightarrow\mathbb{R}\" are computable? (note the domain and codomain are now the reals).<\/span><\/p>\n

\"emperor\"<\/a>\u00a0\u00a0\"Penrose_question\"<\/a><\/p>\n

Computable reals<\/strong><\/p>\n

Suppose we take a real number \"x\". Is \"x\" computable? What do we mean by \"x\" being computable? If we can find an algorithm \"A\" that calculates for each input \"k \in \mathbb{N}\" a rational approximation \"A_k\" of \"x\"; and such that the sequence \"(A_k)\" \"converges fast\" to \"x\" then we say that \"x\" is a computable real. More precisely, a real number \"x \in R\" is computable iff there exists a computable function \"f:\mathbb{N} \rightarrow \mathbb{Q}\" such that \"|f(k) - x| < 2^{-k}\" for each \"k \in \mathbb{N}\". For example, every rational number is computable. The famous number \"\pi\" is computable, and in our previous post we proved<\/a> that \"\sqrt{2}\" is computable. It turns out that the set of computable reals, denoted by \"\mathbb{R}_C\" is a field with respect to addition and multiplication. But there exist real numbers which are not computable. This is easy to see as there is only a countable number of computable functions \"\mathbb{N}\rightarrow\mathbb{N}\", and since we know that \"\mathbb{R}\" is uncountable, so we have more real numbers than we have possible algorithms, we conclude that there must be a real number that is not computable. One example of an uncomputable real is the limit of a Specker sequence<\/a>. And one other interesting one is the Chaitin constant<\/a>. In fact, if we take any recursively enumerable but non-recursive set \"A \subseteq \mathbb{N}\", then the number \"\alpha = \sum_{i \in A} 2^{-i}\" is an example of a real number which is not computable.<\/span><\/p>\n

Computable sequences of reals<\/strong><\/p>\n

If we have a sequence of computable reals \u00a0\"(x_n)\" (and hence a sequence of algorithms) we may ask if this sequence is computable i.e. is there a single algorithm that describes the whole sequence? If there exists a computable function \"f : \mathbb{N}^2 \rightarrow \mathbb{Q}\" \u00a0such that \u00a0<\/span><\/p>\n

  <\/span>   <\/span>\"\[ |f(n,k) - x_n| < 2^{-k}\]\"<\/p>\n

for each \"n,k \in \mathbb{N}\" then we say that \"(x_n)\" is a computable sequence of reals. We have seen that each rational number is computable, but this is not true for sequences of rational numbers! One example of a sequence that has each term computable and also computable as a sequence of reals, but it is not computable as a sequence of rationals is the following [Pour-el, Richards]:<\/p>\n

Example<\/strong>:<\/p>\n

Take any recursively enumerable but non-recursive set \"A \subseteq \mathbb{N}\" and let \"a:\mathbb{N} \longrightarrow \mathbb{N}\" be a one-to-one recursive function which enumerates \"A\".<\/span><\/p>\n

Let \"f:\mathbb{N} \longrightarrow \mathbb{Q}\" be given by<\/p>\n

  <\/span>   <\/span>\"\[ f(n) = 2^{-m}, \mbox{ if } m = a(n) \mbox{ for some } m \\, 0 \mbox{ otherwise. } \]\"<\/p>\n

Then \"f\" is not computable (as a sequence) of reals but \"f\" is not computable as a sequence of rationals.<\/span><\/p>\n

Computable real functions<\/strong><\/p>\n

Real functions which are the main object of study in analysis can be studied in this computability setting, a function \"f:\mathbb{R} \rightarrow \mathbb{R}\" is computable iff \u00a0<\/span><\/p>\n

    \n
  1. it maps computable sequences to computable sequences i.e. \"f(x_i)\" is computable for every computable sequence \"(x_i)\";<\/li>\n
  2. it is effectively uniformly continuous;<\/span><\/li>\n<\/ol>\n

    The fundamental theorem of computable analysis is that every computable real function is continuous.<\/p>\n

    There is also a notion of computability for the process of integration, derivation, solving partial differential equations, etc. and we shall look into that topic in another post.<\/p>\n

    Computable subsets of the Euclidean space<\/strong><\/p>\n

    \"computable_circle\"<\/a>

    Unit circle approximated with dyadic points<\/p><\/div>\n

    Next, let's look at the subsets of the euclidean space \"\mathbb{R}^n\" and ask a simple question: what subsets are computable? First, note that saying \"S\" is computable iff its indicator function <\/p>\n

      <\/span>   <\/span>\"\[\chi_S(x) =\begin{cases} 1, & x \in S \\ 0, & x \not \in S \end{cases}\]\"<\/p>\n

    is computable is not a useful definition since the indicator function is not continous except when \"S =\mathbb{R}^n\" or \"S=\emptyset\". A subset \"S\" of \"\mathbb{R}^n\" is computable iff the function \u00a0\"\mathbb{R}^n \rightarrow \mathbb{R}\" defined as \"x \mapsto d(x, S)\" is a computable function. For example, take the unit circle in \"\mathbb{R}^2\". \u00a0<\/p>\n

      <\/span>   <\/span>\"\[\mathbb{S}^1 = \{(x,y): x^2 + y^2 =1\}\]\"<\/p>\n

    . The distance function is <\/p>\n

      <\/span>   <\/span>\"\[d((x,y), \mathbb{S}^1) = |x^2 + y^2 - 1|, \forall x,y \in \mathbb{R}^2.\]\"<\/p>\n

    \u00a0 These are just some basic definitions and facts, but also interesting questions are studied in computable analysis like for example what mappings preserve computability of objects? \u00a0Is for example the Mandelbrot set computable? What about Julia Sets? For them, there are nice results presented in the book \"Computability of Julia Sets\" by\u00a0Braverman and\u00a0<\/span>Yampolsky.<\/b> <\/span><\/em>Although Julia Sets have been thoroughly researched in the book,\u00a0<\/span>for\u00a0<\/span>the Mandelbrot set we still don't know the answer.<\/span><\/p>\n

    Basically for anything we do in analysis (finding derivatives, integration, finding roots, solving PDEs ...) we may ask: \"Is it computable?\" and that is a topic for another post.<\/p>\n

    (to be continued)<\/p>\n

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

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

    What is Computable analysis anyway? Roger Penrose in his book \"The emperors new Mind\" asked an interesting question regarding the Mandelbrot set: \"Is the Mandelbrot set recursive?\" The term \"recursive\" is an old name for \"computable\" and has nothing to do with recursion in programming. Classical computability theory (also known as recursion theory) is a […]<\/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":[4],"tags":[],"class_list":["post-191","post","type-post","status-publish","format-standard","hentry","category-computable-analysis"],"_links":{"self":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/191","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=191"}],"version-history":[{"count":66,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/191\/revisions"}],"predecessor-version":[{"id":1327,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/posts\/191\/revisions\/1327"}],"wp:attachment":[{"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/media?parent=191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/categories?post=191"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/konrad.burnik.org\/wordpress\/wp-json\/wp\/v2\/tags?post=191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}