# Questions tagged [computable-analysis]

The computable-analysis tag has no usage guidance.

19
questions

**1**

vote

**0**answers

35 views

### Classification and computation of the entanglements of pairs of planar curves

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

393 views

### Is the Hilbert space-filling curve bijective over computable numbers?

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

137 views

### Partial computability results on integrals over open intervals

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 quaternion has a square root?

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

76 views

### Buridan's principle in computable analysis

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

277 views

### Is there a computable homeomorphism between two different Cartesian powers of the computable real numbers?

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

### Banach spaces: A ball being a subset of the interior of the union of two balls

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

157 views

### Are these two definitions of arithmetical hierarchy of real numbers equivalent?

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

174 views

### Is the following product-like space a Polish space?

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

330 views

### floating point representation via the perspective of TTE/computable analysis

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

**11**

votes

**1**answer

1k views

### Is this property equivalent to Lusin's property (N) for continuous functions?

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

751 views

### An NP-hard $n$ fold integral

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

921 views

### Can nonstandard analysis be used to prove results in constructive or computable analysis?

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

**5**

votes

**1**answer

295 views

### tennenbaum phenomena for the reals?

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

401 views

### The complexity of the leading fractional bit of a power of a rational number

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

901 views

### Simple example of a sequence without computable modulus of convergence

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

307 views

### Computable distribution on [0,1] with C-infinity distribution function

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

**5**

votes

**5**answers

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

**11**

votes

**3**answers

1k views

### Differentiability of computable functions

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