Questions tagged [computable-analysis]
The computable-analysis tag has no usage guidance.
24
questions
2
votes
1
answer
141
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 ...
- 3,579
17
votes
1
answer
993
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 ...
- 44.5k
7
votes
1
answer
432
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, ...
- 5,837
6
votes
1
answer
355
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 ...
- 3,629
9
votes
0
answers
251
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 ...
- 2,358
2
votes
0
answers
44
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
875
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
150
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 ...
- 3,579
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"...
- 3,579
1
vote
0
answers
93
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
308
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 '...
- 7,669
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 \...
- 98
4
votes
1
answer
189
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:\...
- 2,008
4
votes
1
answer
192
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-...
- 5,837
3
votes
1
answer
406
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 ...
- 449
13
votes
2
answers
2k
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 ...
- 1,551
17
votes
1
answer
813
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\...
- 607
12
votes
1
answer
1k
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,837
6
votes
2
answers
392
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 ...
- 61
11
votes
1
answer
407
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 ...
- 4,536
5
votes
2
answers
1k
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 ...
- 672
2
votes
0
answers
316
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) = ...
- 2,107
4
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 ...
- 51
12
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 ...
- 908