Why is Kleene's notion of computability better than Banach-Mazur's? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:49:49Z http://mathoverflow.net/feeds/question/21947 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21947/why-is-kleenes-notion-of-computability-better-than-banach-mazurs Why is Kleene's notion of computability better than Banach-Mazur's? Neel Krishnaswami 2010-04-20T08:36:50Z 2010-04-21T20:52:40Z <p>In <a href="http://mathoverflow.net/questions/21745/the-difference-between-the-recursive-and-the-effective-topos" rel="nofollow">this post</a> about the difference between the recursive and effective topos, Andrej Bauer said:</p> <blockquote> <p>If you are looking for a deeper explanation, then perhaps it is fair to say that the Recursive Topos models computability a la Banach-Mazur (a map is computable if it takes computable sequences to computable sequences) and the Effective topos models computability a la Kleene (a map is computable if it is realized by a Turing machine). In many respects Kleene's notion of computability is better, but you'll have to ask another question to find out why :-)</p> </blockquote> <p>So I'm asking: </p> <p>1) What is "computability a la Banach-Mazur"? I would guess it has something to do with Baire spaces and computable analysis, but I don't really know.</p> <p>2) Why is Kleene's notion of computability better?</p> http://mathoverflow.net/questions/21947/why-is-kleenes-notion-of-computability-better-than-banach-mazurs/21979#21979 Answer by Andrej Bauer for Why is Kleene's notion of computability better than Banach-Mazur's? Andrej Bauer 2010-04-20T16:09:57Z 2010-04-21T04:25:31Z <p>This answer requires a bit of background.</p> <p><strong>Definition 1:</strong> a <em>numbered set</em> $(X,\nu_X)$ is a set $X$ together with a partial surjection $\nu_X : \mathbb{N} \to X$, called a <em>numbering</em> of $X$. When $\nu_X(n) = x$ we say that $n$ is a <em>code</em> for $x$.</p> <p>Numbered sets are a generalization of Gödel codes. Some typical examples are:</p> <ul> <li>$\mathbf{N} = (\mathbb{N}, \mathrm{id}_\mathbb{N})$ is the standard numbering of natural numbers.</li> <li>$\mathbf{P} = (P, \phi)$ where $P$ is the set of partial computable maps and $\phi$ is a standard enumeration of partial computable maps.</li> <li>$\mathbf{R} = (R,\nu_R)$ where $R$ is the set of computable reals and $\nu_R(n) = x$ when, for all $k \in \mathbb{N}$, $\phi_n(k)$ outputs (a code of) a rational number $q$ such that $|x - q| &lt; 2^{-k}$.</li> </ul> <p>Numbered sets can be used to give effective structure to many mathematical structures. What should we take as a morphism between numbered sets? Presumably a map $f : X \to Y$ should be considered a morphism from $(X,\nu_X)$ to $(Y,\nu_Y)$ when it is "computable" in a suitable sense. We understand fairly well what it means to have a computable map $\mathbb{N} \to \mathbb{N}$, namely computed by a Turing machine, so let us take that for granted. It is easy to extend computability of sequences of numbers to computability of arbitrary sequences:</p> <p><strong>Defintion 2:</strong> A map $s : \mathbb{N} \to X$ is a <em>computable sequence</em> in $(X,\nu_X)$ when there exists a computable map $f : \mathbb{N} \to \mathbb{N}$ such that $s(n) = \nu_X(f(n))$ for all $n \in \mathrm{dom}(\nu_X)$.</p> <p>Now suppose we think a bit like analysts. One way to define a continuous map is to say that it maps convergent sequences to convergent sequences. We could mimick this idea to define general computable maps.</p> <p><strong>Definition 3:</strong> A function $f : X \to Y$ where $(X,\nu_X)$ and $(Y,\nu_Y)$ are numbered sets is <em>Banach-Mazur computable</em> when $f \circ s$ is a computable sequence in $(Y,\nu_Y)$ whenever $s$ is a computable sequence in $(X,\nu_X)$.</p> <p>How good is this notion? And how does it compare to the following notion, which is taken as the standard one nowadays?</p> <p><strong>Definition 3:</strong> A function $f : X \to Y$ where $(X,\nu_X)$ and $(Y,\nu_Y)$ are numbered sets is <em>Markov computable</em>, or just <em>computable</em>, when there exists a partial computable map $g : \mathbb{N} \to \mathbb{N}$ such that $f(\nu_X(n)) = \nu_Y(g(n))$ for all $n \in \mathrm{dom}(\nu_X)$.</p> <p>In other words, $f$ is <em>tracked</em> by $g$ in the sense that $g$ does to codes what $f$ does to elements. (Note: in <a href="http://mathoverflow.net/questions/21745" rel="nofollow">this MO</a> I attributed this notion of computability to Kleene, but I think it's better to attach Markov's name to it, if any.)</p> <p>Every Markov computable function is Banach-Mazur computable. In some cases the converse holds as well. For example, every Banach-Mazur computable map $\mathbf{N} \to \mathbf{N}$ is Markov computable. However, this is not the case in general:</p> <ol> <li><p>R. Friedberg demonstrated that there is a Banach-Mazur computable map $\mathbf{N}^\mathbf{N} \to \mathbf{N}$ which is not Markov computable. [R. Friedberg. 4-quantifier completeness: A Banach-Mazur functional not uniformly partial recursive. Bull. Acad. Polon. Sci. Sr. Sci. Math. Astr. Phys., 6:1–5, 1958.]</p></li> <li><p>P. Hertling constructed a Banach-Mazur computable map $\mathbf{R} \to \mathbf{R}$ which is not Markov computable. [P. Hertling. A Banach-Mazur computable but not Markov computable function on the computable real numbers. In Proceedings ICALP 2002, pages 962–972. Springer LNCS 2380, 2002.]</p></li> <li><p>A. Simpson and I showed that there is a Banach-Mazur computable $\mathbf{X} \to \mathbf{R}$ that is not Markov computable when $\mathbf{X}$ is any inhabited computable complete separable metric space computably without isolated points. [A. Bauer and A. Simpson: <a href="http://math.andrej.com/2004/07/27/two-constructive-embedding-extension-theorems-with-applications-to-continuity-principles-and-to-banach-mazur-computability/" rel="nofollow">Two Constructive Embedding-Extension Theorems with Applications to Continuity Principles and to Banach-Mazur Computability</a>, Mathematical Logic Quarterly, 50(4,5):351-369, 2004.]</p></li> </ol> <p>What this says is that Banach-Mazur computability is too general because it admits functions that cannot be computed in the standard sense of the word, i.e., computed by Turing machine (in terms of codes).</p> http://mathoverflow.net/questions/21947/why-is-kleenes-notion-of-computability-better-than-banach-mazurs/22116#22116 Answer by Andrej Bauer for Why is Kleene's notion of computability better than Banach-Mazur's? Andrej Bauer 2010-04-21T20:52:40Z 2010-04-21T20:52:40Z <p>Jacques asks about a "kernel" idea for the three counter-examples. I am not sure I can answer the question well. The most general result, namely the third one, is really a consequence of Friedberg's result. Peter Hertling's construction is an adaptation of Friedberg's result (although not an obvious one by any means), too. So the question is, what did Friedberg do? I must admit I cannot explain this succinctly, perhaps it's best if you have a look at Section 9 of</p> <blockquote> <p>P. Hertling, "A Banach–Mazur computable but not Markov computable function on the computable real numbers", Annals of Pure and Applied Logic 132 (2005) 227–246.</p> </blockquote> <p>Suffice it to say that the construction involves showing that a certain set of indices of B-M computable functionals is a $\Pi^0_4$-set, but the corresponding set of indices of Markov computable functionals is $\Sigma^0_4$-complete and contained in the first set, therefore the two sets differ. Now if there is anyone around who can explain in simple terms what $\Sigma^0_4$-complete sets are like, I would love to hear it.</p>