All Questions
Tagged with computability-theory computable-analysis
17 questions
2
votes
0
answers
142
views
Can a path in Kleene's $\mathcal{O}$ enumerate all of the computable reals via uniform diagonalization?
It's a well-known fact that there are computable diagonalization functions on Baire space $\mathbb{B} = \mathbb{N}^\mathbb{N}$ (i.e., functions which take a sequence $(r_i)_{i\in \mathbb{N}}$ of ...
- 12.5k
3
votes
0
answers
87
views
Is the probability distribution of a graphon given as a graph limit computable?
Let $G_i$ be a sequence of finite graphs that is Cauchy in the space of graphons. That is, for every $\epsilon \in \mathbb Q_+$ there is a $N \in \mathbb N$ such that $$\forall n, m > N. \delta_\...
- 6,353
7
votes
2
answers
230
views
Why does Weihrauch reducibility make use of multi-functions?
This is probably a kinda dumb question, but why is Weihrauch reducibility defined in terms of multi-functions (i.e. why isn't it just the degree structure of regular functions under that reducibility)?...
- 4,359
6
votes
3
answers
392
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 ...
- 32.5k
5
votes
1
answer
118
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 ...
- 342
2
votes
1
answer
145
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$...
- 63.9k
6
votes
1
answer
421
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 ...
- 4,717
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 ...
- 4,713
9
votes
0
answers
306
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 ...
- 4,359
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 ...
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 ...
2
votes
0
answers
103
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 ...
3
votes
0
answers
186
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 \...
- 128
4
votes
1
answer
221
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:\...
- 6,287
3
votes
1
answer
446
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 ...
- 6,287
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 ...
- 8,481
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 ...
- 44.4k