Questions tagged [computable-analysis]
The computable-analysis tag has no usage guidance.
19
questions
2
votes
1
answer
97
views
Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain
The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation $f : \subseteq A \to B$ means a partial function. By $\Sigma^{\omega}$ and $\Sigma^{\ast}$ we denote the set of ...
2
votes
5
answers
437
views
A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise
Consider the following definition:
A number $x \in \mathbb R$ is computable, if there exists a (one-tape) Turing machine which (running infinitely long) writes the binary expansion of $x$ onto its ...
19
votes
3
answers
638
views
Computation of reals: floating point vs TTE vs domain theory vs etc
Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised ...
0
votes
2
answers
151
views
Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?
"any two representations of reals which are acceptable are actually computably isomorphic",please see here for reference
where may proof of this theorem be found, and what is the the computational ...
-1
votes
1
answer
87
views
For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another
Any computable number may have different representations of finite length . For example,$\sqrt{2}$ may be represented as root of equation, or as a (shortest for a universal Turing Machine)program of ...
4
votes
1
answer
278
views
Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$
Is it decidable whether a computable analytic function $f(x_1,x_2,\dots,x_n)$ over $\mathbb{R}$, $\mathbb{C}$ in a semi-algebraic or semi-analytic domain is identically zero? Is there any algorithm?
...
11
votes
2
answers
403
views
How to judge the definition of computational complexity of reals is natural or suitable?
As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in ...
6
votes
1
answer
1k
views
What is a reasonable representation/encoding of objects? [closed]
Question
What is a reasonable representation of objects (for computability)?
What is the criteria that we should apply to see if a representation is reasonable?
This answer by Andrej suggests that ...
1
vote
1
answer
110
views
Delimiting the roots of a polynomial
Given a polynomial of degree $n$, namely, $y=a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0$, with $a_i\in \mathbb{R}$, I would to know if it is possible to compute a rational number $K$ such that the ...
13
votes
4
answers
1k
views
Decidability of transcendental numbers
I have a question, whose answer is probably well known, but I can't seem to find anything meaningful after a bit of searching, so I would appreciate some help.
My question is whether it is known that ...
1
vote
1
answer
299
views
Concerning decidability of a problem on real numbers [closed]
This question is an outgrowth of a certain maths problem I've been thinking about.
Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer ...
13
votes
6
answers
3k
views
Functions that typed lambda calculus cannot compute
I just want to know some examples of the functions that can be computed by the untyped lambda calculus but not by typed lambda calculi.
As I am a beginner, some reiteration of background information ...
18
votes
2
answers
7k
views
Complexity of computing the discrete Fourier transform?
What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers?
The classical algorithm for fast Fourier transforms, ...
2
votes
0
answers
81
views
mean/integral, except where positive differences between values and "mean" are weighted differently from negative differences?
Given a curve $f(x)$ (for $x \in [0,1]$), and a line $y=a$, let $U$ be the total area below $f$ and above $a$, and let $L$ be the total area above $f$ and below $a$. If $L=U$, this means that $a =\...
6
votes
2
answers
553
views
Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)
I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis.
A very general question:
Most algorithms compromise of
...
1
vote
1
answer
170
views
Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?
Let's say I had an optimization problem
$$ \min_{x \in D} f(x) $$
Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist.
Imagine I had a ...
43
votes
3
answers
4k
views
What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?
Background
The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
27
votes
6
answers
2k
views
How are real numbers specified in computation?
This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real ...
4
votes
3
answers
588
views
What applications of Cantor space are there?
Are there well-established applications of the Cantor space ($2^\omega$) in computer science, other than those connected with computable real arithmetic?
John Tucker's page Computation on Topological ...