Questions tagged [computable-analysis]
The computable-analysis tag has no usage guidance.
19
questions
1
vote
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
5answers
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
3answers
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 ...
