Questions tagged [computable-analysis]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
110 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 ...
poeaqnwgo's user avatar
1 vote
0 answers
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 ...
Ma Joad's user avatar
  • 1,591
5 votes
1 answer
99 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 ...
Gro-Tsen's user avatar
  • 29.8k
6 votes
3 answers
338 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 ...
Gro-Tsen's user avatar
  • 29.8k
2 votes
1 answer
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$...
Dominic van der Zypen's user avatar
2 votes
1 answer
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 ...
wlad's user avatar
  • 4,792
20 votes
1 answer
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 ...
Andrej Bauer's user avatar
  • 47.7k
8 votes
1 answer
500 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, ...
Jason Rute's user avatar
  • 6,237
6 votes
1 answer
395 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 ...
Arno's user avatar
  • 4,356
9 votes
0 answers
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 ...
Sam Sanders's user avatar
  • 3,901
2 votes
0 answers
50 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 ...
Klaus Weihrauch's user avatar
4 votes
1 answer
1k 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 ...
Mehmet Ozan Kabak's user avatar
1 vote
1 answer
158 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 ...
wlad's user avatar
  • 4,792
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"...
wlad's user avatar
  • 4,792
1 vote
0 answers
98 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 ...
MaudPieTheRocktorate's user avatar
13 votes
1 answer
353 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 '...
James Hanson's user avatar
  • 10.3k
3 votes
0 answers
184 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 \...
Amin's user avatar
  • 128
4 votes
1 answer
208 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:\...
Alex Mennen's user avatar
  • 2,090
4 votes
1 answer
212 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-...
Jason Rute's user avatar
  • 6,237
3 votes
1 answer
434 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 ...
SorcererofDM's user avatar
14 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 ...
Linda Brown Westrick's user avatar
17 votes
1 answer
862 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\...
Ganesh's user avatar
  • 617
13 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 ...
Jason Rute's user avatar
  • 6,237
6 votes
2 answers
405 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 ...
Leon Horsten's user avatar
11 votes
1 answer
416 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 ...
Victor Miller's user avatar
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 ...
Mateus Araújo's user avatar
2 votes
0 answers
326 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) = ...
Nate Ackerman's user avatar
5 votes
5 answers
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 ...
user9679's user avatar
13 votes
3 answers
2k 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 ...
sdcvvc's user avatar
  • 928