# Questions tagged [computable-analysis]

The computable-analysis tag has no usage guidance.

The computable-analysis tag has no usage guidance.

24
questions

2
votes

1
answer

141
views

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 ...

17
votes

1
answer

993
views

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 ...

7
votes

1
answer

432
views

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
votes

1
answer

355
views

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 ...

9
votes

0
answers

251
views

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 ...

2
votes

0
answers

44
views

Let $C$ is the set of continuous $f:[0;1]\to \mathbb R^2$ with $\|f\|=\max_t\|f(t)\|$. For $f,g\in C$ let $(f,g)\in E$ iff $\{f(0),f(1)\}\cap {\rm Range}(g)=\emptyset$ and $\{g(0),g(1)\}\cap {\rm ...

3
votes

1
answer

875
views

The Hilbert curve is a continuous space-filling curve that maps $I$ to $I^n$ where $I$ denotes the unit interval [1]. Like all other space-filling curves, it is not one-to-one. I am wondering if the ...

1
vote

1
answer

150
views

It's well known in Type 2 Effectivity that integration over a compact interval is computable. So what about integration over an open interval? What rigorous computability results exist?
My thoughts ...

20
votes

2
answers

2k
views

Is it possible to constructively prove that every $q \in \mathbb H$ has some $r$ such that $r^2 = q$? The difficulty here is that $q$ might be a negative scalar, in which case there might be "too many"...

1
vote

0
answers

93
views

In (Lamport, 2012), Lamport proposes the principle
A discrete decision based upon an input
having a continuous range of values cannot be made within a bounded length of time.
I think it could be ...

12
votes

1
answer

308
views

It's well know that it is surprisingly difficult to prove that $\mathbb{R}^n$ and $\mathbb{R}^m$ are not homeomorphic for $n\neq m$. Commonly proofs go through Brouwer's fixed point theorem, which is '...

2
votes

0
answers

179
views

Let $X$ be a separable reflexive Banach space and let $A$, $B_1$, and $B_2$ be three closed balls in $X$. Is there a `handy' necessary and sufficient condition for checking whether $A \subseteq (B_1 \...

4
votes

1
answer

189
views

Zheng and Weihrauch (http://www-sst.informatik.tu-cottbus.de/~wwwti/zheng/publications/1999/mfcs99.pdf) define a real number $x$ to be $\Sigma_n$ if and only if there is a computable function $f:\...

4
votes

1
answer

192
views

Let $\mathcal{M}_1(\mathbb R)$ denote the space of Borel probability measures on $\mathbb R$. The space is a Polish space (a space which admits a complete, separable, metric) using, say the Levy-...

3
votes

1
answer

406
views

Floating point numbers are not compatible with the usual theory of type 2 theory of effectivity (TTE), and not even the real-RAM model; there are functions that are computable in one model but not ...

13
votes

2
answers

2k
views

A function $F:[0,1]\rightarrow\mathbb{R}$ satisfies Lusin's (N) property if for every measure zero set $A\subseteq [0,1]$, $F(A)$ has measure zero. (This includes the assertion that $F(A)$ is ...

17
votes

1
answer

813
views

We are given rational numbers $[c_1, c_2, \ldots, c_n]$ and $v$ from the interval $[0,1]$.
Consider the $n$-fold integral
$$
J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} d\...

12
votes

1
answer

1k
views

Nonstandard analysis is a useful tool which can be used to prove a number of results in analysis.
Question
Can it also be used to prove results in computable or constructive analysis?
If so, what are ...

6
votes

2
answers

392
views

Let $\mathfrak{M} = \langle R, +,\times,> \rangle$ be such that $R$ is the set of real numbers and $\mathfrak{M} \models RA^1$ (the first-order axioms for the reals). Do we have characterisations ...

11
votes

1
answer

407
views

On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are ...

5
votes

2
answers

1k
views

Can anyone give a simple example of a sequence that converges, but there's no computable function that gives $N$ as a function of $\epsilon$, i.e., the modulus of convergence is not computable?
In ...

2
votes

0
answers

316
views

Does anyone know of an easily-describable distribution on $[0,1]$ with a density $p$ (with respect to Lebesgue measure) that satisfies the following properties:
$p$ is $C^\infty$
$p(0) = a$, $p(1) = ...

4
votes

5
answers

1k
views

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 ...

12
votes

3
answers

1k
views

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 ...