All Questions
Tagged with computability-theory real-analysis
9 questions
5
votes
1
answer
359
views
Infinite multiplicity set of continuous functions
Definitions:
Fix a function $f:\mathbb{R}\to\mathbb{R}$ such that $f$ obtains each value only finite (possibly $0$) number of times. We say $E \subset \mathbb{N}$ is the "multiplicity set" ...
- 103
8
votes
1
answer
1k
views
Why don't Zeilberger and Gosper's algorithms contradict Richardson's theorem?
Richardson's theorem proves that whether an expression A is equal to zero is undecidable. A is in this case an expression, constructed from $x,e^x,\sin(x)$ and the constant function $\pi$ and $\ln(2)$ ...
- 157
17
votes
1
answer
580
views
Aperiodic monotile in $\mathbb{R}$
Motivation. Recently a group of researchers found an aperiodic monotile in $\mathbb{R}^2$, answering a long-standing question. There are many results in higher dimensions, so let's explore the lower ...
- 48.9k
0
votes
1
answer
156
views
Realizability of metric matrices
We call an $n\times n$-matrix ${\bf A}\in \text{Mat}(n\times n, \mathbb{R})$ a metric matrix if
${\bf A}_{ii} = 0$ for all $i\in \{1,\ldots,n\}$,
${\bf A}_{ij} = {\bf A}_{ji}$ for all $i,j \in \{1,\...
- 48.9k
5
votes
1
answer
315
views
Is $\mathbb{Q}$ the orbit of a continuous function that is computable when restricted to $\mathbb{Q}$?
In the previous post What is the smallest set of real continuous functions generating all rational numbers by iteration? I asked for the smallest set of continuous real functions that could generate $\...
- 4,862
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
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 ...
- 459
6
votes
2
answers
308
views
Recent trends in effective analysis
The references listed at http://en.wikipedia.org/wiki/Computable_analysis have all been published 30-15 years ago. Are the approaches which these references expose still up-to-date and relevant to the ...
user60665
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 ...
- 1,601