Questions tagged [computable-analysis]
computability and complexity in real or complex analysis
13
questions
2
votes
0
answers
114
views
Decide whether a polynomial has a root
Let $A$ be a ring such that all elements of $A$ are complex computable numbers. I'm interested in knowing whether the decision problem that asks, given $P\in A[X]$, if $P$ has a root in $A$ is ...
- 86
3
votes
2
answers
691
views
What is the "continuity" as a term in computable analysis?
Background
I once implemented a datatype representing arbitrary real numbers in Haskell. It labels every real numbers by having a Cauchy sequence converging to it. That will let $\mathbb{R}$ be in the ...
- 335
2
votes
0
answers
57
views
Semidecidable properties of computable reals
By computable real I mean $x\in\mathbb{R}$ such that there is some computable total function $p_x$ that takes a natural number $n$ and returns a dyadic rational $r$ such that $|x-r|<2^{-n}$. I ...
- 21
2
votes
0
answers
255
views
What is the computational cost of automatic differentiation compared to symbolic and numerical differentiation?
Automatic differentiation is a set of techniques to numerically evaluate the derivative of a function.
Quoting from Wikipedia (emphasis mine):
These classical methods run into problems: symbolic ...
- 286
0
votes
2
answers
216
views
What is the relationship between two definitions of Turing-computability of a partial function?
When one wants to know that whether a partial function $f \colon \Sigma^{*} \supsetneq \mathrm{dom}(f) \rightarrow \Sigma^{*}$ is Turing-computable, there are two methods that I think they are both ...
- 623
11
votes
2
answers
588
views
Decidable properties of computable reals
Is "Rice's theorem for the computable reals" -- that is, no nontrivial property of the number represented by a given computable real is decidable -- true?
Does this correspond in some direct way to ...
- 213
2
votes
2
answers
119
views
What does Sigma notation mean, in the context of computability of functions?
I was reading a paper on the computability of AIXI [1] and came across the notion of $\Sigma^0_n$-computability for real-valued functions in section 2.3.
I'd like to read about this in more detail.
...
- 369
2
votes
2
answers
235
views
Is Newton's Method to compute the zeros of a function an algorithm?
Looking for Newton's method in Wikipedia, I read the following:
In numerical analysis, Newton's method (also known as the
Newton-Raphson method), named after Isaac Newton and Joseph Raphson,
is ...
- 19.4k
15
votes
2
answers
991
views
Are there established complexity classes with real numbers?
A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of:
I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with ...
- 72k
2
votes
1
answer
139
views
Poly-time computability of inversion of poly-time real functions
At pp. 7-8 of Ker-I Ko's Computational Complexity of Real Functions (1991), the following is stated for one dimensional cases:
Let $INV_1$ be the operator that maps a one-to-one function $f:[0,1]\...
- 1,614
4
votes
1
answer
832
views
How does automatic differentiation work?
What is the intuitive idea behind automatic differentiation?
If I have a program which computes $f(x, y)=x^2+yx$, which steps lead to the program which computes the derivative $df/dx$ of f?
...
user13187
7
votes
3
answers
1k
views
Is a PDA as powerful as a CPU?
This is a question I have stumbled upon in my exam revision and I find it intriguing:
My computer is blue and it has a massive graphics card and a DVD and every-
thing so which is more powerful: my ...
Mike Howard
11
votes
1
answer
633
views
A continuous optimization problem that reduces to TSP
Suppose I am given a finite set of points $p_1,p_2,..p_n$ in the plane, and asked to draw a twice-differentiable curve $C(P)$ through the $p_i$'s, such that its perimeter is as small as possible. ...
- 1,489