Questions tagged [computable-analysis]

computability and complexity in real or complex analysis

Filter by
Sorted by
Tagged with
2
votes
0answers
96 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 ...
3
votes
2answers
572 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 ...
2
votes
0answers
142 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 ...
2
votes
0answers
39 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 ...
2
votes
2answers
105 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. ...
0
votes
2answers
134 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 ...
10
votes
2answers
399 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 ...
2
votes
2answers
192 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 ...
15
votes
2answers
878 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 ...
2
votes
1answer
112 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]\...
4
votes
1answer
714 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? ...
7
votes
3answers
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 ...
11
votes
1answer
608 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. ...