# Questions tagged [computable-analysis]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
1 vote
105 views

### Integration in polynomial time

The work of Friedman and Ko and Müller guarantee the polynomial time computability of the integrals of analytic functions inside the circle of convergence. But do algorithms have practical value? Is ...
1 vote
50 views

### Reference for a proof of Ceitin's theorem (Borel computable = Markov computable)?

Ceitin's theorem says that if a function $\mathbb R_c \to \mathbb R_c$ is Markov computable, then it is Borel computable (or TTE-computable). I find this theorem on Klaus Weihrauch's Computable ...
• 1,591
98 views

### Understanding the definition of a (computably / continuously) “transparent” function

The following definitions of a “transparent function” are essentially taken from references [1] (where it is called a “jump operator”), [2] and [3], except that the variation “primitively recursively ...
• 29.7k
332 views

### Intuition behind Kleene's “second algebra” $\mathcal{K}_2$

The “second Kleene algebra” $\mathcal{K}_2$ is defined, e.g. here on nLab, or in section 1.4.3 of van Oosten's book Realizability: an Introduction to its Categorical Side (2008), or as example 3.4 of ...
• 29.7k
140 views

### Computability of fillability of unit cube in $\mathbb{R}^n$ by $k$ $\varepsilon$-balls

Let $\mathbb{N}$ denote the set of positive integers. We define a relation $R \subseteq \mathbb{N}^4$ in the following way: $(p,q,n,s)\in R$ if and only if there is $S\subseteq [0,1]^n$ with $|S| = s$...
158 views

### LLPO as constructivity/computability for dense subsets

LLPO is the statement $\forall x \in \mathbb R. x \leq 0 \vee x \geq 0.$ The statement should be understood as a fragment of the Law of Excluded Middle, rather than a statement about the ordering of ...
• 4,782
1k views

### Is the one-point compactification of $\mathbb{N}$ computably countable?

The one-point compactification $\mathbb{N}_\infty$ of $\mathbb{N}$ is obtained from the discrete space $\mathbb{N}$ by adjoining a limit point $\infty$. It may be identified with the subspace of ...
• 47.6k
495 views

### Are representations in computable analysis the equivalent to countably-generated condensed sets?

This is the first in a pair of questions. For the other see here. Dustin Clausen and Peter Scholze have a theory of condensed sets, which is a slightly different take on topology. For most cases, ...
• 6,207
391 views

### Computing the complex roots of a monic polynomial

The map from monic complex polynomials to the unordered tuples of their roots (each appearing according to its multiplicity) is computable. This seems to have been known for a long time, and with ...
• 4,346
283 views

### Coding third-order objects via second-order ones

As is well-known, the language of second-order arithmetic only has variables for natural numbers and sets of natural numbers. Higher-order objects, like functions on $\mathbb{R}$, have to be ...
• 3,841
50 views

• 128
208 views

• 2,209
2k views

### Uncomputability of the identity relation on computable real numbers

Let $f_{=}$ be a function from $\mathbb{R}^{2}$ be defined as follows: (1) if $x = y$ then $f_{=}(x,y) = 1$; (2) $f_{x,y} = 0$ otherwise. I would like to have a proof for / a reference to a textbook ...
• 61
Call a computable function a total function $\mathbb{R} \to \mathbb{R}$, for which there exists a Turing machine outputting arbitrary close approximation to $f(x)$ given arbitrary close approximation ...