Questions tagged [computable-analysis]

computability and complexity in real or complex analysis

Filter by
Sorted by
Tagged with
2 votes
0 answers

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 ...
Rémi's user avatar
  • 86
3 votes
2 answers

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 ...
Dannyu NDos's user avatar
2 votes
0 answers

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 ...
user96217's user avatar
2 votes
0 answers

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 ...
glS's user avatar
  • 286
0 votes
2 answers

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 ...
Blanco's user avatar
  • 623
11 votes
2 answers

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 ...
Shachaf's user avatar
  • 213
2 votes
2 answers

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. ...
Manlio's user avatar
  • 369
2 votes
2 answers

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 ...
babou's user avatar
  • 19.4k
15 votes
2 answers

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 ...
Raphael's user avatar
  • 72k
2 votes
1 answer

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]\...
user13675's user avatar
  • 1,614
4 votes
1 answer

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? ...
user avatar
7 votes
3 answers

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 ...
user avatar
11 votes
1 answer

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. ...
PKG's user avatar
  • 1,489